项目Euler #7:代码中有什么问题吗？

Question

--这与Euler #7项目有关，它是关于寻找10001个素数的。

在这段代码中，如果我在第二个for循环中使用k*k<=i，程序会变得更快，但它给了我第10000个质数作为答案。但是当我使用k<=i或k<=i/2时，程序变慢了，但是给出了正确的答案。

根据我的逻辑，一个特定的数字可以除以<1-the square root of that number>范围内的数字。该范围内的任何除数在范围<square root - (number/2)>中都有相应的除数。

那么，为什么我在这两种方法中得到了两个不同的答案？

下面是代码：

#include<stdio.h>

int main()
{
    int i;
    int k;
    int x;
    int y=0;

    for(i=1;i<100000000;i++){
        x = 0;
        /*finding whether the number has more than 2 divisor(exept 1 and the number itself)*/
        for(k=1;k*k<=i;k++){
            if(i%k == 0){
                x++;
            }
        }
        if(x==2){
            y++;
        }

        if(y == 10001){ 
            printf("\n%d",i);
            break;
        }
    }

    printf("\n\n");
    return 0;
}

这是另一个：

#include<stdio.h>

int main()
{
    int i;
    int k;
    int x;
    int y=0;

    for(i=1;i<100000000;i++){
        x = 0;
        /*finding whether the number has more than 2 divisor(exept 1 and the number itself)*/
        for(k=1;k<=i/2;k++){
            if(i%k == 0){
                x++;
            }
        }
        if(x==1){
            y++;
        }

        if(y == 10001){ 
            printf("\n%d",i);
            break;
        }
    }

    printf("\n\n");
    return 0;
}

Answer 1

您应该使用埃拉托斯提尼，它的速度要快得多。

您的第一段代码将认为i=1是自k=1：k*k <= i以来的素数(x==1)，但是第二段代码将不认为它是素数，因为对于k=1：k > i/2。i/2是整数除数，将被截断为0。