找出200万以下所有素数的总和.项目欧拉,C

Question

所以,一切似乎都运行良好,但程序没有给我正确的答案.我的是142,915,960,832,而应该是142,913,828,922.差异是2,131,910(如果我仍然可以减去纸上的数字哈哈),我不知道我从哪里获得这两百万.谁能帮助我？

#include <stdio.h>
#include <math.h>

#define BELOW 2000000

int isaprime (int num);

int main (void) {

    int i;
    float sum = 0;

    for (i = 2; i < BELOW; i++) {

            if (isaprime(i) == 1) {
                    sum = sum + i;
                    printf ("\n%d\t%.1f", i, sum);
            }
    }

    getch();
    return 0;
}

int isaprime (int num) {

    int i;

    for (i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) {
                    return 0;
            }
            else {
                    ;
            }
    }

    return 1;
}

Answer 1

使用float就像sum是问题.的最大整数k,使得从所有整数[-k, k]是恰好在32位浮点表示的是2 ^ 24 ¹ ; 之后你会开始失去一些整数的精度.由于你的总和超出了这个范围,所以你会失去精确度并且所有的赌注都会被取消.

您需要更改为更大的类型long(假设它在您的计算机上为64位).进行更改,您将得到正确的答案(就像我对您的代码所做的那样):

[ec2-user@ip-10-196-190-10 ~]$ cat -n euler.c
     1  #include <stdio.h>
     2  #include <math.h>
     3  
     4  #define BELOW 2000000
     5  
     6  int isaprime (int num);
     7  
     8  int main (void) {
     9  
    10      int i;
    11      long sum = 0;
    12  
    13      for (i = 2; i < BELOW; i++) {
    14  
    15              if (isaprime(i) == 1) {
    16                      sum = sum + i;
    17              }
    18      }
    19      printf("sum: %ld\n", sum);
    20  
    21      return 0;
    22  }
    23  
    24  int isaprime (int num) {
    25  
    26      int i;
    27  
    28      for (i = 2; i <= sqrt(num); i++) {
    29              if (num % i == 0) {
    30                      return 0;
    31              }
    32              else {
    33                      ;
    34              }
    35      }
    36  
    37      return 1;
    38  }
[ec2-user@ip-10-196-190-10 ~]$ gcc euler.c -lm
[ec2-user@ip-10-196-190-10 ~]$ ./a.out
sum: 142913828922

¹:在尾数23位明确加一隐藏位.

Answer 2

正如@LeeDanielCrocker所说,这是Eratosthenes筛选的一个实现,它可以即时解决问题:

#include <stdio.h>
#include <string.h>

#define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0)
#define SETBIT(x, i) x[i>>3] |= (1<<(i&7));
#define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;

long long sumPrimes(int n) {
    char b[n/8+1];
    long long i, p;
    long long s = 0;

    memset(b, 255, sizeof(b));
    for (p=2; p<n; p++) {
        if (ISBITSET(b,p)) {
            //printf("%d\n", p);
            s += p;
            for (i=p*p; i<n; i+=p) {
                CLEARBIT(b, i); }}}
    return s; }

int main(void) {
    printf("%lld\n", sumPrimes(2000000));
    return 0; }

在ideone,返回30毫秒.下面显示的优化版本仅在奇数上筛选并且分别处理2,在ideone上以零时间(小于10毫秒)运行.

#include <stdio.h>
#include <string.h>

#define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0)
#define SETBIT(x, i) x[i>>3] |= (1<<(i&7));
#define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;

long long sumPrimes(int n) {
    int m = (n-1) / 2;
    char b[m/8+1];
    int i = 0;
    int p = 3;
    long long s = 2;
    int j;

    memset(b, 255, sizeof(b));

    while (p*p < n) {
        if (ISBITSET(b,i)) {
            s += p;
            j = (p*p - 3) / 2;
            while (j < m) {
                CLEARBIT(b, j);
                j += p; } }
        i += 1; p += 2; }

    while (i < m) {
        if (ISBITSET(b,i)) {
            s += p; }
        i += 1; p += 2; }

    return s; }

int main(void) {
    printf("%lld\n", sumPrimes(2000000));
    return 0; }

如果你对素数编程感兴趣,我谦虚地在我的博客上推荐这篇文章 ; 它描述了上面给出的两种算法,涵盖了解决Project Euler中素数问题所需的所有算法,并包括C语言和其他四种语言的源代码.