Prime Gap

　連続した二つの素数pとp+nの間の、連続したn-1個の合成数（1とその数自身以外の約数を持つ数。素数でない自然数）の列の長さnを素数間隔と呼ぶ。
例として、二つの素数23と29(23+6)の素数間隔は、間の素数でない自然数が24,25,26,27,28の5個であるから、6となる。

　問題は正整数kがあたえられるので、kを含む素数間隔を求めるというもの。
ただし、便宜上kが素数間隔を含まない場合は長さは0と見なす。
　例としてkが10の場合、10は素数でないので、10より大きい素数11と、10より小さい素数7の差である4が10を含む素数間隔となる。

入力

　連続した各行にはそれぞれ一つの正整数がある。
その正整数は1より大きく、100000個の素数を持つ1299709以下である。
入力の終わりは0のみの行で指される。

出力

連続した各行には負でない整数が出力される。
それは入力された正整数に対応した素数間隔を出力する。
ただし入力が合成数なら素数間隔を、そうでないなら0を出力する。
余分な文字は出力しない。

アルゴリズム

　配列の要素が、添え字の素数間隔を示す配列を作る。

　STEP.1
0~1299709までの配列を確保し、全てに0を代入。

　STEP.2
エラトステネスのふるいを用い、素数を判別。
配列の添え字が素数でない場合はその配列の要素に-1が代入される。
素数の場合は0のまま。

　STEP.3
最後尾の素数から、一つずつその前の素数を引いていき、素数の間の合成数に-1の変わりに素数間隔を代入する。

#define MAXを変化させた場合のSTEP.1〜STEP.3の計算時間

#define MAX 1299710
0.01user 0.03system 0:00.19elapsed 23%CPU (0avgtext+0avgdata 108032maxresident)k
0inputs+0outputs (457major+0minor)pagefaults 0swaps

#define MAX 12997100
0.03user 0.00system 0:02.24elapsed 1%CPU (0avgtext+0avgdata 108032maxresident)k
0inputs+0outputs (457major+0minor)pagefaults 0swaps

#define MAX 129971000（メモリ消費500Mくらい)
0.03user 0.00system 0:23.92elapsed 0%CPU (0avgtext+0avgdata 108032maxresident)k
0inputs+0outputs (457major+0minor)pagefaults 0swaps

問題解決時間

テキストのサンプル
0.01user 0.01system 0:00.17elapsed 17%CPU (0avgtext+0avgdata 108032maxresident)k
0inputs+0outputs (457major+0minor)pagefaults 0swaps

1〜1299709までの数字
0.01user 0.01system 0:02.29elapsed 1%CPU (0avgtext+0avgdata 108032maxresident)k
0inputs+0outputs (457major+0minor)pagefaults 0swaps

#include<stdio.h>
#include<stdlib.h>
#define MAX 1299710
int main(void){
	unsigned int counter,counter2,primegap,temp;
	static int a[MAX];	//a[0]〜a[1299709]までの配列を確保(1299710x4B=5198840B=5MB)
	
//配列の初期化
	for(counter=0;counter<MAX;counter++)
		a[counter]=0;	
	
//配列の添え字の数が素数の場合0,素数でない場合-1が代入された配列を得る	
	for(counter=2;(counter*counter)<MAX;counter++){
		while(a[counter]!=0)//
			counter++;
		for(counter2=2;(temp=counter2*counter)<MAX;counter2++)
			a[temp]=-1;	//素数の整数倍に素数でないことを示す-1を代入
	}
	
//素数でない場合に代入されている-1を、その数を含む素数間隔に置き換える
	counter2=MAX-1;
	while(counter2!=2){
		counter=counter2-1;
		while(a[counter]<0)
			counter--;	//現在の素数の値(counter2)よりも小さい素数を探す
		primegap=counter2-counter;	
		//現在の素数の値(counter2)とそれより一つ小さい素数の素数間隔を得る

		while(--counter2!=counter)
			a[counter2]=primegap;	
		//現在の素数とそれより一つ小さい素数の間の合成数に素数間隔を代入する
	}

//入出力の設定 
	int k;
	FILE *fpi,*fpo;	//fpi 読み込むファイル fpo 書き込むファイル
	if((fpi=fopen("B2.in","r"))==NULL){
		fprintf(stderr,"NO:B.in");
		exit(-1);
	}
	if((fpo=fopen("Result.txt","w"))==NULL){
		fprintf(stderr,"ERROR:CAN'T MAKE OUTPUT FILE");
		exit(-2);
	}
	while((fscanf(fpi,"%d",&k)!=EOF) && (k!=0))
		fprintf(fpo,"%d\n",a[k]);
	fclose(fpi);
	fclose(fpo);
	return 0;			
}

ツムラ_メモ

大失敗を繰り返す。