找到所有的素数低于两百万总和。项目欧拉，C [英] Find the sum of all the primes below two million. Project euler, C

问题描述

所以，一切似乎都很好地工作，但该方案并没有给我正确的答案。我的是142915960832，而应该是142913828922。该型差分是2131910（我是否还可以减去在纸上哈哈号），我不知道在哪里我得到这两个百万。谁能帮助我？

 的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆math.h中GT;＃定义低于200万INT isaprime（INT NUM）;诠释主要（无效）{    INT I;
    浮总和= 0;    对于（i = 2; I＆LT;下面，我++）{            如果（isaprime（ⅰ）== 1）{
                    总和=总和+ I;
                    的printf（\\ n％d个\\ T％.1F，我，总和）;
            }
    }    残培（）;
    返回0;
}INT isaprime（INT NUM）{    INT I;    对于（i = 2; I＆LT; =开方（NUM）;我++）{
            如果（NUM％我== 0）{
                    返回0;
            }
            其他{
                    ;
            }
    }    返回1;
}
 

解决方案

使用 浮动 作为之的问题。最大的整数 K 使得来自所有的整数 [ - K，K] 是的究竟的在32位浮点再presentable为2 ^ 24 ¹ ;之后，你将开始在一些整数损失precision。由于您的总和，通过一个荒谬的保证金，你输了precision的范围之外，所有的赌注都关闭。

您需要更改为更大的类型，如长（假设这是你的机器上64位）。做出改变，你会得到正确的答案（因为我有你没有code）：

  [EC2用户@ IP-10-196-190-10〜] $猫-n euler.c
     1＃包括LT＆;＆stdio.h中GT;
     2＃包括LT＆;＆math.h中GT;
     3
     4＃定义低于200万
     五
     6 INT isaprime（INT NUM）;
     7
     8 INT主要（无效）{
     9
    10 INT I;
    11长总和= 0;
    12
    13（I = 2; I＆LT;下面，我++）{
    14
    15，如果（isaprime（我）== 1）{
    16总和=总和+ I;
    17}
    18}
    19的printf（总和：％ld的\\ n，总和）;
    20
    21返回0;
    22}
    23
    24 INT isaprime（INT NUM）{
    25
    26 INT I;
    27
    28（I = 2; I＆LT; =开方（NUM）;我++）{
    29，如果（NUM％我== 0）{
    30返回0;
    31}
    32其他{
    33;
    34}
    35}
    36
    37回1;
    38}
[EC2用户@ IP-10-196-190-10〜] $ GCC euler.c -lm
[EC2用户@ IP-10-196-190-10〜] $ ./a.out
和：142913828922
 

¹ ：在尾数23位明确加上一个隐藏的位

So, everything seems to be working nicely, but the program doesn't give me the correct answer. Mine is 142,915,960,832, whereas it should be 142,913,828,922. The differece is 2,131,910 (if I still can subtract numbers on paper haha) and I have no idea where did I get those two millions. Could anyone help me?

#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;
}

解决方案

Using float as the sum is the problem. The largest integer k such that all integers from [-k, k] are exactly representable in 32-bit float is 2^24¹; after that you will start losing precision in some integers. Since your sum is outside that range that, by an absurd margin, you lose precision and all bets are off.

You need to change to a larger type like long (assuming it's 64-bits on your machine). Make the change, and you'll get right answer (as I did with you code):

[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 explicit bits in the mantissa plus one hidden bit.

这篇关于找到所有的素数低于两百万总和。项目欧拉，C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！