总计2000000以下的素数

我正在尝试这个程序来查找所有素数低于200万的总和，但出于某种原因，我想出了一个远低于我应该预期的数字。总计2000000以下的素数

这是我的代码。一个合作工作表示，我可能不会用我的程序捕捉所有素数，但他不知道C++，我不明白我是如何错过它们的。

#include <iostream> 

using namespace std; 

int main() 
{ 
    int a = 500000; 
    int e = 0; 

    // this is an array to hold all the prime number i find, 
    // it's initialized to the arbitrarily high number of 500000 
    int list[a]; 

    //here i am initializing the first members of my list to the first primes 
    list[0] = 2; 
    list[1] = 3; 
    list[2] = 5; 
    a = 3; // i set a = 3 to catch the next coming prime of 7 
    for (int c = 5; c < 2000000; c++) 
    { 
     // this bool is for prime catching, 
     // if d is false then the number will not be saved into the array 
     bool d = false; 

     // this bool is for an exit statement in the following iterative loop, 
     // if it's false the loop will exit 
     bool h = true; 
     for (int i = 0; list[i] < c/2 + 1 && h == true; i++) 
     { 
      // this checks to see if a number is evenly 
      // divisable by any of my primes so far 
      if (c % list[i] == 0) 
      { 
       d = false; 
       h = false; 
      } 
     } 
     if (d == true) 
     { 
      list[a] = c; // if i find a prime i save it into my array 
      e += c; // if i find a prime i sum it to my total 
      a++; 
     } 
    } 
    cout << e; 
}

来源

2013-03-22 elder south

项目欧拉问题？查看[Eratosthenes的筛子]（http://en.wikipedia.org/wiki/Sieve_of_eratosthenes）。它的速度非常快，可以达到一定的数值，我相信有1000万。 – Marlon 2013-03-22 15:57:04

@Marlom的确，问题10. – Rapptz 2013-03-22 15:58:51

看起来你正在做[Eratosthenes筛]（https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）困难的方式。 – 2013-03-22 15:59:34

d永远是虚假的。没有任何代码将其设置为true。

此外，您需要在10（2 + 3 + 5）处开始e。

来源

2013-03-22 15:57:38

试试这个:)

#include <iostream> 
using namespace std; 
int main(){ 
    bool prime; 
    int num = 200000; 
    int sum = 0; 
    for (int i=3; i<=num; i++){ 
     prime = true; 
     for(int j=2; j<=i/2; j++){ 
      if(i%j == 0) prime = false; 
     } 
     if(prime) sum+=i; 
    } 
    cout << sum; 
}

来源

2013-03-22 16:11:23

从技术上讲，这有效，但有更多有效的方法。 [这YouTube视频播放列表]（https://www.youtube.com/playlist?list=PLbg3ZX2pWlgKZ0eR9lviOkeagDuSPl89K）是理解素数和如何有效地找到它们的好资源。 – 2013-03-22 16:14:55

在我看来，最有效的方式找到，如果数是素数是：

检查数量少于4（<=3），那么它是素数。假设只有正整数参与。
否则，检查它是否是偶数 - 然后它不是质数。
如果超过3个，甚至不是 - 从3到所有数字的平方根检查它，跳过所有校验。如果它是任何数字的倍数，那么它不是素数。否则它是素数。

在C++中的话：

bool IsPrime(unsigned int nCheck) 
{ 
    assert(nCheck>0); 

    if(nCheck<=3) 
    return true; 

    if(nCheck%2==0) 
    return false; 

    for(int nCounter = 3; nCounter <= sqrt(nCheck); nCounter += 2) // Skip evens 
    { 
     if(nCheck % nCounter == 0) 
      return false; 
    } 
    return true; 
}

任何数量是被1至该数的平方根。例如，100可以被最大10整除。即使它可以被50整除，也可以被5整除。所以，只需从1到10进行检查。

来源

2013-03-23 07:37:57 Ajay

总计2000000以下的素数

回答

相关问题