ディリクレの算術級数定理（ICPCの過去問題）

Question

ICPCの過去問題ですが、以下の仕様を1秒以内に実行を行いたいです。
現在は1秒を超えています。
どのようにすればよろしいでしょうか？

 こんばんは，選手諸君．

a と d が互いに素な正の整数ならば， a から始まり d ずつ増える 等差数列 a, a + d, a + 2d, a + 3d, a + 4d, ... には無限個の素数が含まれる． このことはディリクレの算術級数定理として知られている． ガウス(Johann Carl Friedrich Gauss, 1777 - 1855)が予想していたことを， 1837年に ディリクレ(Johann Peter Gustav Lejeune Dirichlet, 1805 - 1859)が 証明した．

たとえば， 2から始まり3ずつ増える等差数列

2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, ... 

は，無限個の素数

2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, ... 

を含む．

そこで君の使命だが， 与えられた正整数 a と d と n に対して， この等差数列に含まれる n 番目の素数を求めるプログラムを書くことにある．

例によって，君もしくは君の仲間が疲れはて，あるいは混乱しても，当局はいっさい関知しないからそのつもりで． なお，この審判システムは3時間で自動的に停止する．成功を祈る．

#include <stdio.h>

int sosu(int n){
//素数判定関数    
    int i;
    
	if(n < 2)
		return 0;
	//もしnが2より小さい場合、0を返す。	

	if(n == 2)
		return 1;
    //もしnが2だった場合、1を返す
	for(i = 2; i <= n/2; i++){
		if(n%i == 0)
			return 0;
		//もし、nがほかの数（i）で割り切れたら素数ではないので、0を返す。	
	}

	return 1;
	//素数であるときのみ1を返す。
}

int main(int argc, char *argv[]){

	int a, d, n;
	//初項a、公差d、n番目の素数　それぞれの変数を宣言。
	while(1){
    //標準入力がある限りループを回す。
		scanf("%d %d %d", &a, &d, &n);
		//標準入力で、初項a、公差d、n番目の素数を読み取る。
		
		if(a == 0 && d == 0 && n == 0){
		//もし、標準入力に「0　0　0」が来たら、終了。
			break;
		}
		
		int m = a;
		//mには、初期値に初項aを代入。
		int count = 0;
		//countには初期値を設定。

		while(1){
		
			if(sosu(m)){
			    //素数判定
			    count++;
			}
				
			if(count == n){
			//もし、n番目の素数にたどり着いた場合
				printf("%d\n", m);
			//標準出力で素数表示。	
				break;
			}

			m += d;
			//mに公差dを足していく。
		}
	}


    return 0;
} 

Answer 1

a, d, n の値により、また実行環境により時間は違うので、一概にどうすれば一秒切れるかというのは言えません。

for(i = 2; i <= n/2; i++){

とりあえずここは無駄が多いですね。
たとえば n が 100 の場合、i は 50 までカウントアップされますが、10 まででいいはずです。100 を 10 で割ると 10 で、これ以上 i を増やすと、割った商は 10 未満、つまり既に確かめた値になります。
条件は i <= n/2 ではなく、i * i <= n にしましょう。

Comments

[Taka787]

とても分かりやすい説明でした。ありがとうございました。ちょっとしたところを変えるだけで、結構実行時間が変わることがわかりました。とても勉強になりました。