Сито реализации Eratosthenes c ++

Question

Я написал эту реализацию Решета Эратосфена на с ++, но всякий раз, когда код достигает 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. Вероятно, это достаточно легко исправить. Но программа не печатает последний бит, где она дает вам решение. Weird.

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 элементов. Идея сита заключается в том, что вы берете большое количество вещей и отфильтровываете те, которые не соответствуют. Что бы это ни стоило, 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;

Answer 2

Вот исправленная версия для сравнения:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    const int sieve_size = 1 << 20;
    const int solution_number = 10001;
    int number_of_primes = 0;
    vector<bool> sieve(sieve_size, true);

    for (int i = 2; i < sieve_size; i++)
    {
        if (!sieve[i])
            continue;

        if (++number_of_primes == solution_number)
        {
            cout << "The 10 001st prime number is:" << i << endl;
            return 0;
        }

        for (long long j = i*2; j < sieve_size; j += i)
            sieve[j] = false;
    }
}

Вывод:

The 10 001st prime number is:104743