Cプロジェクトオイラー数は、だから、イム解決の問題10を

Question

を素数、そして一つの解に到達：

int primo(long num){ 

long pd; 

pd = num/2; 

while(pd > 1 && num%pd != 0){ 
    pd--; 
} 
if (pd == 1) 
    return 1; 
else 
    return -1;} 

私のマシンで実行時には、700のようなものだった：プリモがある

acu = 0; 
for(i=2;i<=2000000;i++){   
    if(primo(i)== 1){ 
     acu = acu + i; 
    } 
} 

秒。次にコード内でこれを変更します。

int primo(long num){ 

long pd; 

pd = lround(sqrt(num)); 

while(pd > 1 && num%pd != 0){ 
    pd--; 
} 
if (pd == 1) 
    return 1; 
else 
    return -1;} 

実行時間は15秒です。 num/2とlround（sqrt（num））の違いは何故ですか？ primo関数の最後の呼び出しの数学的な差があるので

Answer 1

：さらに

num = 2000000 
num/2 => 1000000 
lround(sqrt(2000000)) = 1414 

、primoは、forループで繰り返し呼び出されています。 （numが素数であるとき）

Answer 2

単に最悪の場合には最初の実装を引き起こすので、第2の実施が必要とする時間の方が低いnum/2よりもはるかに低いnum/2回のループが、第2の意志ループsqrt(num)回、そしてもちろんsqrt(num)の意志最初のものよりも時間がかかります。

EDIT：

あなたがより速くあなたはそれがある使用2よりも別の実装をしたい場合：

int primo(long num){ 
    if(num==2) return 1; //2 is even but prime so we check it herer cause the next test will return 0 for even bumbers 
    if(num%2==0) return 0; //if it is a multiple of 2 it is not a prime number so we do not loop in this case 

    long nb_sqrt= lround(sqrt(num)); 
    if(nb_sqrt%2==0) nb_sqrt++; //start from an odd number (explained in the loop) 

    while(num%nb_sqrt != 0) nb_sqrt-=2; //decrements by 2 since the number is not a multiple of 2 (already checkef) so it will not be divided by an even number 

    return nb_sqrt==1; 
}