高速化について全くわからないので教えて欲しいです。入力した値に近い素数を見つけるという課題なのですが入力した値が大きい場合、処理できず反応しません。提出が火曜の夜までなので助けて下さい、、

Question

前提・実現したいこと

高速化（大きい値を入力しても処理できるようになりたい）

C言語の授業でVsコードを使っています。今プログラミングをしたのは入力した値に近い素数を見つけるというものです。
高速化ができてないため数が大きいと処理できません。助けて下さい、、提出火曜の夜までなんです、、

//説明

#include<stdio.h>
long long main(void){
long long N, D;

//整数Nの設定
printf("正の整数Nを入力してください。");
scanf("%lld", &N);

//error判定
if(N<=0){
printf("もう一度入力して下さい。");
return 0;
}

// i=0から始まりマイナスしていく
else{
for (long long i = 0;;i--){

// D=0スタート
D=0;

// j=1スタートでプラスしていく、jはN+i以下で設定
for (long long j=1;j<=N+i;j++){

// N+iをjで割った時のあまりが0
if((N+i)%j == 0){

// Dに足していく
D++;
}
}

// 約数が２個の時
if(D==2){
printf("%lldに近い素数は",N);
printf("%lldです。\n", N+i);

// 素数を見つけたからおしまい
break;
}
}
}
return 0;
}
//

Comments

[Zuishin]

エラトステネスの篩を使ってください。
十分時間はあります。

[nopainnogain]

エラトステネスの篩とはなんですか？
詳しく聞きたいです。

[Zuishin]

Google というサイトを知りませんか？

[nopainnogain]

仕組みはなんとなく理解したのですがそこからプログラミングすることができません

[m.ts10806]

>調べてもよくわかりません、、
質問に何も書いてなければ調べてないのと同じです。
見るのは赤の他人ですから。

Answer 1

// j=1スタートでプラスしていく、jはN+i以下で設定
for (long long j=1;j<=N+i;j++){

N+i=10の場合の約数は1,2,5,10ですが10%2=0と10%5=0は10/2=5より自明です。
つまり、j<=sqrt(N+i)までで十分です。
また、2以外すべての素数は奇数なので、2だけループの外に出せばj++ではなくj+=2でよいことになります。

さらに高速化したい場合、32bitまでの素数を全て事前に計算しておけば64bitまでの合成数は全て32bitの素数で割り切れます。
もっと高速化したい場合、ミラーラビンテストを2,325,9375,28178,450775,9780504,1795265022で行います。

Comments

[nopainnogain]

わかりやすい回答ありがとうございます！
とりあえずやってみます。

[asm]

コードを見ていてもう一つ気づきました。
全ての約数を求めてそれが2個である数を素数としていますが
jがN+iではないときに、2か3以上の数jで割り切れたらその時点で合成数という事になります。

Answer 2

入力した値が大きい場合、処理できず反応しません。

入力値の上限設定がない以上、いくら対応しても限界が来ます。
設問に問題がある以上、回答は無理かと。