あなたはそれらが素数であるかどうか259=3,814,697,265,625の数をチェックしています。これは多くの素数判定であり、常に時間がかかります。すべての配列エントリ（in）が0（テストで0が素数と見なされることを気にしないでください）で、試行除算ループが実行されないという最良の場合（パフォーマンスのため）でも、m実行には数時間かかります。のすべてのエントリmが正の場合、コードはそのままで数百年または数千年実行されます。それ以降、各数値は50,000,000を超える数値で試行分割されます。
プライムチェックを見て、
check_prime = 1;
for ( y = 2; y <= num/2; y++)
{
if ( num % y == 0 )
check_prime = 0;
}
最初の明白な非効率性は、除数が見つかり、の複合性がnum確立された後でもループが続くことです。結果がわかったらすぐにループから抜け出します。
check_prime = 1;
for ( y = 2; y <= num/2; y++)
{
if ( num % y == 0 )
{
check_prime = 0;
break;
}
}
テストするすべての数値が素数であるという不幸なケースでは、それは何も変わりませんが、すべて（またはほぼすべて、ほぼすべての値が十分に大きい場合）の数値が合成数である場合、実行時間を1分の1に短縮します。少なくとも5000。
次のことはあなたがに分割することnum/2です。それは必要ありません。なぜあなたはで止まらnum/2ず、で止まるのnum - 1ですか？さて、あなたがの最大の適切な除数は、の場合numよりも大きくすることはできないことを理解したnum/2ので(num >) k > num/2、2*k > numそしてnumはの倍数ではありませんk。
それは良いことです、誰もがそれを見るわけではありません。
しかし、あなたはその思考の列をさらに追求することができます。num/2がの約数である場合num、それはnum = 2*(num/2)（を除いて整数除算を使用することを意味しますnum = 3）。しかし、それnumは偶数であり、その複合性はすでに2による除算によって決定されているため、num/2成功した場合、による除算は試行されません。
では、検討する必要のある最大の除数の次の候補は何でしょうか。num/3もちろん。しかし、それがの除数であるnum場合、num = 3*(num/3)（を除いnum < 9て）そして3による除算はすでに問題を解決しています。
続けて、とがの約数である場合k < √num、それはより小さな約数、つまり（おそらくさらに小さな約数）を持っていることがわかります。num/knumnum = k*(num/k)numk
したがって、の最小の自明でない約数numは。以下です√num。したがって、ループは、、y <= √numまたはに対してのみ実行する必要がありますy*y <= num。その範囲で除数が見つからない場合numは、素数です。
ここで、ループするかどうかという疑問が生じます
for(y = 2; y*y <= num; ++y)
また
root = floor(sqrt(num));
for(y = 2; y <= root; ++y)
1つ目は、各反復でループ条件に対して1回の乗算を必要とし、2つ目は、ループ外の平方根の計算を必要とします。
どちらが速いですか？
これは、の平均サイズとnum、多くが素数であるかどうか（より正確には、最小の素数除数の平均サイズ）によって異なります。平方根の計算には乗算よりもはるかに長い時間がかかります。そのコストを補うために、ループは（平均して）多くの反復で実行する必要があります。たとえば、「多く」が20を超えるか、100を超えるか、1000を超えるかは異なります。ここでおそらくそうであるように、numより大きい10^8場合は、おそらく平方根を計算する方が良い選択です。
これで、試行除算ループの反復回数を合成か素数かに制限し√num、テストされた数の中に素数がいくつあるかに関係なくnum、実行時間を少なくとも5000分の1に短縮しました（すべてm[index] > 0、つまり常に）。 num >= 10^8。ほとんどの値numが素因数が小さい複合材料である場合、通常、素因数のテストに実行時間がほぼ完全に使用される範囲で、削減係数ははるかに大きくなります。
除数候補の数を減らすことにより、さらなる改善を得ることができます。numが4、6、8、...で割り切れる場合は、2でも割り切れるのでnum % y、偶数に対して0が得られることはありませんy > 2。つまり、これらすべての部門は不要です。特別なケーシング2と2のステップで除数候補をインクリメントすることによって。
if (num % 2 == 0)
{
check_prime = 0;
} else {
root = floor(sqrt(num));
for(y = 3; y <= root; y += 2)
{
if (num % y == 0)
{
check_prime = 0;
break;
}
}
}
実行する分割の数と実行時間は約半分になります（偶数の作業が無視できるほどの悪いケースを想定しています）。
yこれで、が3の倍数（3自体以外）である場合は常に、が3の倍数でないnum % y場合にのみ計算されるnumため、これらの除算も不要です。y3を特殊なケースに入れ、3で割り切れない奇数のみを実行することでそれらを排除できます（で始まりy = 5、2と4を交互にインクリメントします）。それは残りの仕事のおよそ3分の1を切り落とします（十分な悪いケースが存在する場合）。
その除去プロセスを続けると、素数であるかどうかを見つけるために、超えない素数numで除算するだけで済みます。√num
したがって、通常は、チェックする最大の平方根を超えない素数を見つけてnum、配列に格納してループすることをお勧めします。
root = floor(sqrt(num));
for(k = 0, y = primes[0]; k < prime_count && (y = primes[k]) <= root; ++k)
{
if (num % y == 0)
{
check_prime = 0;
break;
}
}
取ることができる最大値numが十分に小さい場合を除いて、たとえば、常に持ってnum < 2^31いる場合は、ビットふるいでその限界までの素数を見つけてnum、一定時間で素数であるかどうかを調べる必要があります（ふるい2 ^31ビットの場合は256MBかかります。奇数のフラグしかない場合（偶数かどうかを確認するために特別なケースが必要）、一定時間でnum素数を確認するために必要なのは128 MBだけで< 2^31、必要なスペースがさらに削減されます。ふるいのために可能です）。
これまでのところ、プライムテスト自体についてです。
m配列に2または5で割り切れる数値が含まれている場合は、ループを並べ替えi、最も外側のループを作成し、m[i]が2または5で割り切れる場合は、内側のループをスキップすることをお勧めします。他のすべての数値は累乗で乗算されます。追加する前に10のnum場合、2の倍数になります。5であり、素数ではありません。
しかし、それにもかかわらず、コードの実行にはまだ時間がかかります。間違ったデザインの9つのネストされたループリーク。
あなたがやろうとしていることは何ですか？たぶん私たちは正しいデザインを見つけるのを手伝うことができます。