c - 欧拉计划 #7 : is anything wrong in the code?

Question

这与 Project Euler #7 有关，即寻找第 10001 个素数。

在这段代码中，如果我使用 k*k<=i在第二个 for 循环中，程序变得更快，但它给了我第 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

你应该使用 Sieve_of_Eratosthenes相反，它要快得多。

您的第一个代码将考虑 i=1素数 ( x==1 ) 因为 k=1 : k*k <= i ，但是您的第二个代码不会将其视为质数，因为对于 k=1 : k > i/2 . i/2是整数除法，将被截断为 0 .