c++ - 埃拉托色尼筛法 C++ 实现错误

Question

我用 C++ 编写了这个埃拉托色尼筛法的实现，但是每当代码达到 59(第 16 个素数)时，它就会停止工作。它只能在我的旧机器上达到 37。当我调试程序时，所有变量似乎都工作正常；该程序只是崩溃。在这里:(我知道它有很多评论，很多是不必要的。)

// Problem 7:What is the 10 001st prime number?

/*This program generates a list of prime numbers and uses the Sieve of Eratosthenes to find them.
 *This is done by crossing out multiples of the first known prime (2), taking the first number
 *not yet crossed out, and setting that as the next prime to "sieve" with.
 */

#include "stdafx.h"
#include <iostream>

using namespace std;

int main()
{
    int placeholder;                    //added at the end to prevent window from closing
    const int sieve_size = 10000;       //amount of #s to sieve through
    const int solution_number = 10001;  //# of primes to generate
    long long solution;                 //the 10 001st prime #
    long long current_sieve;            //current # sieving with
    int number_of_primes = 1;           //we know the first prime -- 2
    long long *primes = new long long [number_of_primes];
    primes[0] = 2;                  //2 is the first prime
    bool flag_havePrime = 0;        //whether we have our next prime yet; used when saving a prime
    bool sieve[sieve_size] = {0};   //0 is "could-be-prime" (not composite), 1 is composite.
    sieve[0] = 1;   //0 and 1 are not prime #s
    sieve[1] = 1;

    for (int i = 0; number_of_primes <= solution_number; i++)   //each loop sieves with a different prime
    {
        current_sieve = primes[i];

        //This next loop sieves through the array starting with the square of the number we will sieve with,
        //this optimizes the run time of the program.
        for (long long j=current_sieve*current_sieve; j <= sieve_size; j++)
            if (j%current_sieve == 0) sieve[j] = 1;

        /*This loop gets our next prime by looking through the array until
         *it encounters a number not crossed out yet. If it encounters a prime,
         *it increments the number of primes, then saves the new prime into
         *primes[]. It also prints that prime (for debugging purposes).
         *The "for" loop ends when it finds a prime, which it knows by encountering
         *the "havePrime" flag. This needs to be reset before every run.
         */

        for (long long j = primes[number_of_primes-1]+1; flag_havePrime == 0; j++)
        {
            if (sieve[j] == 0)
            {
                number_of_primes++;
                primes[number_of_primes-1] = j;             //because array counting starts @ 0
                cout << primes[number_of_primes-1] << endl; //because array counting starts @ 0
                flag_havePrime = 1;
            }
        }
        flag_havePrime = 0; //resetting this flag
    }
    solution = primes[number_of_primes-1];  //because array counting starts @ 0
    delete[] primes;
    primes = 0;

    cout << "The 10 001st prime number is:\n";
    cout << solution << endl;
    cin >> placeholder;
    return 0;
}

我认为这可能是一个溢出问题？

---

这是一个仅包含更改的更新代码段:

const int sieve_size = 500000;
long long *primes = new long long [solution_number];

尽管调试会返回(喘气)堆溢出，但运行编译版本不会。编译版本停止在 104759，超过 1。这可能很容易修复。但是该程序不会打印最后一位，它会为您提供解决方案。很奇怪。

Answer 1

int number_of_primes = 1;           //we know the first prime -- 2
long long *primes = new long long [number_of_primes];

这将创建一个单元素数组。我很确定您需要比这更大的东西来存储素数。

具体来说，一旦您开始设置像 primes[11] 这样的值(例如)，您就进入了未定义行为的领域。

也许有一个不同的变量，你可能想考虑在 new 语句中使用大小，轻推，轻推，眨眼，眨眼，点头和点头一样好对一匹瞎马眨眼:-)

---

该代码中还有一些其他问题。最主要的是你的筛子本身只有 10,000 个元素长。筛子的想法是你拿走大量的东西并过滤掉那些不匹配的东西。就其值(value)而言，10,001^st 略低于 105,000，因此您的筛子应该至少有那么大。

其次，我看到人们使用数字的平方来优化因子的查找，但不是以这种方式:

for (long long j=current_sieve*current_sieve; j <= sieve_size; j++)
    if (j%current_sieve == 0) sieve[j] = 1;

你想要的是从当前筛子的两倍开始，每次都添加它，比如:

for (long long j = current_sieve * 2; j < sieve_size; j += current_sieve)
    sieve[j] = 1;