c++ - 2000000以下的素数和

Question

我正在尝试这个程序来找到所有低于 200 万的素数的总和，但由于某种原因，我得出的数字远低于我的预期。

这是我的代码。一位同事说我可能无法用我的程序捕捉所有素数，但他不懂 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; 
}

Answer 1

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

此外，您需要从e10 (2 + 3 + 5) 开始。

Answer 2

试试这个 ：）

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

Answer 3

在我看来，找出数字是否为素数的最有效方法是：

• 检查数字是否小于 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。