c - 求两百万以下的所有素数之和。欧拉计划，C

Question

所以，一切似乎都运行良好，但程序并没有给我正确的答案。我的是 142,915,960,832，而应该是 142,913,828,922。差值是 2,131,910（如果我仍然可以在纸上减去数字哈哈），我不知道我从哪里得到这 200 万。有人可以帮我吗？

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

score 10 · Accepted Answer

使用floatas thesum是问题所在。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 个显式位加上一个隐藏位。

score 6 · Accepted Answer

正如@LeeDanielCrocker 所建议的，这里是埃拉托色尼筛子的一个实现，它可以立即解决问题：

#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以零时间（小于十毫秒）运行。

#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 和其他四种语言的源代码。

score 3 · Accepted Answer

请尝试这种方式，快速简单：

int const MAX = 2000000;

int checkPrime(int n){
    int range = n;
    for (int i = 2; i < range; i++){
        if (n%i == 0){
            return 0;
        }
        range = n / i;
    }
    return 1;
}

int solution(){
    double sum = 0;
    for (int i = 2; i < MAX; i++){
        if (checkPrime(i) == 1){
            sum += i;
        }
    }
    return sum;
}

score 0 · Accepted Answer

您可以使用Sieve 算法，因为这将是最快的：-

在 C++ 中

std::vector<int> generate_primes( int n )
{
    std::vector<bool>sieve( n, true ) ;
    for( std::size_t i = 2 ; i < sieve.size() ; ++i ) if( sieve[i] )
          for( auto j = i*i ; j < sieve.size() ; j += i ) sieve[j] = false ;

    std::vector<int> primes ;
    for( std::size_t i = 2 ; i < sieve.size() ; ++i )
        if( sieve[i] ) primes.push_back(i) ;
    return primes ;
}

score 0 · Accepted Answer

#include<stdio.h>
#define MAX 2000001
long long a[MAX],c=0;
main()
{
     long long i=0,k,j,p,temp=0;
    long long inc=0;
    for(i=0;i<MAX;i++)
    a[i]=i;
    for(j=2;j*j<MAX;j++)
    {   
        temp=j;
        inc=2*temp;
        k=((MAX-1)/temp)-1;
        while(k)
        {
            printf("%d",inc);
            printf("\n");
            if(a[inc]!=0)
            a[inc]=0;
            inc+=temp;
            --k;
        }
    }
    for(p=0;p<MAX;p++)
    {
        if(a[p]!=0)
        c=c+a[p];

        printf("%lld",a[p]);
        printf("\n");
        }
    printf(" The sum is : %lld",c-1);
}

score 0 · Accepted Answer

这是我的 JavaScript 解决方案：

function sumPrimes(num) {

  // determine if a number is prime
  function isPrime(n) {
    if (n === 2) return true;
    if (n === 3) return true;
    if (n % 2 === 0) return false;
    if (n % 3 === 0) return false;

    var  i = 5;
    var  w = 2;
    while (i * i <= n) {
        if (n % i === 0) {
            return false;
        }
        i += w;
        w = 6 - w;
    }
    return true;
  }

  // subtract 1 for 'not being prime' in my context
  var sum = isPrime(num) ? num - 1 : -1;

  for (var x = 0; x < num; x++) {
    if (isPrime(x) === true) {
      sum += x;
    }
  }

  return sum;
}

score 0 · Accepted Answer

    Addition of prime No upto 2 million below is the code. 
     Please let me know    if anyone have doubt.

    <html>

    <body>

    <input id="inp" width="200px"/>
     <input type="button" onClick="onPress()" value="Check"/>

     </body>



      <script>
     function onPress()
      {


       var value= document.getElementById("inp").value;

         var arr=[2,3,5,7], add=17;

       for(var divisor=2; divisor<value; divisor++)
       {
        var prime= true
        if(divisor%2==0 || divisor%3==0 || divisor%5==0 || divisor%7==0)
           {


            prime=false;



             }



                if(prime !=false)
                {

               for(var j=0; j<arr.length; j++)
                {
               if(divisor%arr[j]==0)
                 {

             prime=false;

                }

                }
                }


                if(prime==true)
                  {

                 arr.push(divisor);

                 add+= divisor;


                         }
                        }

                      console.log(add);


                        }





       </script>



       </html>

score 0 · Accepted Answer

虽然这个答案不是完美的，但执行时间不到3 秒。C# 中的代码。

第 1 步 - 省略可被 2,3, 5,7 整除的数字
第 2 步 - 要检查素数，我们不需要将给定数字除以所有数字。使用平方根会将代码减少一半。

    using System;


namespace ProjectEuler
{
    class Program
    {
        static void Main(string[] args)
        {
            long i, j, sum = 17;
            bool flag = true;
            for (i = 2; i < 2000000; i++)
            {
                if ((i % 2) != 0 && (i % 3) != 0 && (i % 5) != 0 && (i % 7) != 0)
                {
                    flag = true;
                    for (j = 2; j <= Math.Sqrt(i); j++)
                    {
                        if (i % j == 0)
                        {
                            flag = false;
                        }
                    }
                    if (flag == true)
                    {
                        sum = sum + i;
                    }
                }

            }
            Console.WriteLine(sum);
            Console.ReadLine();
        }
    }
}

score -2 · Accepted Answer

您可以在c中检查以下代码：

/*Program to print sum of all prime numbers upto 2000000*/

/*To check whether a number is prime or not it takes n^2 time by
  brute force but this program is sqrt(n) according to
  mathematical rules to check prime number efficiently.
*/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 2000000
int main()
{
  int i,j;
  unsigned long int prod=0;
  int prime;
  for(i=2;i<=MAX;i++){
    prime=1;
    for(j=2;j<(int)(sqrt(i)+1);j++){
      if(i%j==0){
        prime=0;
        break;
      }
    }
    if(prime==1){
      prod=prod+i;
    }
  }
  printf("%ld",prod);
  return 0;
}

c - 求两百万以下的所有素数之和。欧拉计划，C

9 回答 9

Related

Reference