C 项目欧拉数素数

Question

所以，我正在解决问题 10，并得出一个解决方案:

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

primo 所在位置:

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 秒。然后我在代码中更改它:

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)) 之间差异如此之大？

Answer 1

只是因为在最坏的情况下(当 num 为素数时)，第一个实现将循环 num/2 次，但第二个实现将循环 sqrt(num) 次，当然 sqrt(num) 比 num/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;
}