c - 打印 64 位素数和

Question

#include<stdio.h>
int main(){
    int n,k=1;
    int i,j;
    unsigned long long int sum=0;
    scanf("%d",&n);
    for(i=2;i<n;i++){
        for(j=2;j<=i;j++){
            if(i%j==0)
                k++;
        }
        if(k==2){
            sum=sum+i;
        }
        k=1;
    }
    printf("%lld",sum);
    return 0;
}

此代码对于输入 1000,10000 工作正常，但对于 100000,1000000 则不行，我的意思是它什么都不打印。我也试过 %I64d 但没有用。
如何打印 sum ？

Answer 1

我建议您在每次迭代时打印总和，而不仅仅是在结束时打印，这样您就可以看到计算的进度。除了更容易调试你的 printf语句，然后您还可以检测到可能的回绕(例如，如果 unsigned long long 不足以求和)。

无论如何 -- 我认为您的问题实际上与您的 printf 有关格式字符串:使用 %llu而不是 %lld .请看下面的代码:

int main(){
    int n,k=1;
    int i,j;
    unsigned long long int sum=0;
    scanf("%d",&n);
    for(i=2;i<n;i++){
        for(j=2;j<=i;j++){
            if(i%j==0)
                k++;
        }
        if(k==2){
            sum=sum+i;
        }
        k=1;
        /* This helps you see what's going on: */
        printf("sum is %llu\n",sum);
    }
    printf("%llu",sum);
    return 0;
}

我用过%llu而不是 %lld ，它工作正常。如果我把它改回 %lld , 每次迭代都不会打印任何内容。

并确保您的输入 ( n ) 不能超过 int 的最大大小在你的平台上。 (但总和可能更大，因为您将其声明为 unsigned long long )。

此外，在检查质数时，您可以进行一些基本的优化:

• 唯一需要检查的偶数是 2。所有其他素数都是奇数。
• 您不需要检查超过 n 的平方根。或者，等价地:假设您正在测试 k 是否整除 n。如果n/k<k (或者如果 k*k>n )，您可以停止测试。

此外，您可以使用 C 中可用的标准 bool 类型。

请参阅下面代码中的注释。

#include<stdio.h>
#include<math.h>
/* stdbool defines the type "bool", which can be "true" or "false": */
#include<stdbool.h>

int main(){
    int n;
    int i,j;

    /* prime is initialized to true, since we presume every number is prime
       until we find a divisor for it */
    bool prime = true;

    /* sum is initialized to zero. */
    unsigned long long int sum=0;

    scanf("%d",&n);

    /* If n=2, the result is zero. But if it's greater than two, we need
       to count 2 and start searching from 3. It's easier this way, because then
       we can use i=i+2 in the for loop. */
    if (n>2)
        sum = 2;

    /* no need to count from 2. We start from 3 and count every two numbers. */           
    for(i=3;i<n;i=i+2){
        /* same here. And, since this is the divisor we're looking for, we only 
           need to go up to sqrt(i). We use the long casting here because checking
           j*j<=i would not fit in an int type if j^2 is greater than the maximum
           int. This is a corner case, that happens for example when i is maxint
           (j-1)^2 is below and and j^2 is above it. */
        for(j=3;(long)j*j<=i;j=j+2)
            if(i%j==0) {
                prime = false;
                /* get out, since we already know that this one is composite! */
                break;
            }

        /* no divisors? add it to sum! */
        if (prime)
            sum = sum + i;

        /* reset prime to true, we'll start again with next i */
        prime = true;

        printf("sum is %llu\n",sum);
    }
    printf("%llu\n",sum);
    return 0;
}

这些是您可以执行的相当简单的优化。还有其他的，有兴趣的可以研究下sieve of Erathostenes或者(如果你喜欢数学)，Miller-Rabin test (这不是确定性的，但可能很有趣)。 C 库 GMP如果您想使用它，可以使用 Miller-Rabin。