Ошибка при реализации решета Эратосфена на c++

Question

Необходимо найти все простые числа, не превосходящие заданного, используя решето Эратосфена. При запуске кода в VS 2019 вылезает ошибка.

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* parr = new int[n];
    for (int i = 0; i <= n; i++)
    {
        parr[i] = i;
    }

    for (int i = 2; i * i <= n; i++)
    {
        for (int j = i * i; j <= n; j += i)
        {
            parr[j] = -1;
        }
    }
    for (int i = 2; i <= n; i++)
    {
        if (parr[i] != -1)
        {
            cout << parr[i] << " ";

        }
    }
    delete[] parr;
    return 0;
}

Answer 1

int* parr = new int[n];

Выделили массив из n элементов, но

for (int i = 0; i <= n; i++)

обращаетесь к n+1 элементу. Выход за границы массива как минимум...

Answer 2

Вот вам готовый вариант на векторе (он меньше массива жрет).

Нарыл где-то в сети и допилил немного.

Вывод закомментирован.

Максимум N (<= 18 446 744 073 709 551 615) - это теоретически с чем оно можнт работать. На деле я с больше чем 10 млрд не тестировал. Компилировал в командной строке MinGW\bin\c++ и MinGW\bin\g++

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <numeric>
#include <fstream>

using namespace std;
 
int main()
{
    setlocale(LC_CTYPE, "russian");

    std::cout << "Введите N (<= 18 446 744 073 709 551 615) ";
    unsigned long long n;
    cin >> n;
    auto start = clock();
    vector<bool> v(n + 1, true);
    v[0] = false;
    v[1] = false;
    
    unsigned long long pp;
    for (unsigned long long p = 2; p <= n; ++p)
    {
        pp = p*p;
        if(pp > n or p >= 4294967296) break;
        if(!v[p]) continue;
        for (unsigned long long d = pp; d <= n; d += p)
        {
            if(!v[d]) continue;
            v[d] = false;
        }
    }
    
    auto finish = clock();
    unsigned long long count = accumulate(v.begin(), v.end(), 0);
    std::cout << "Количество простых чисел от 2 (включительно) до " << n << " (включительно) " << count << std::endl;
 
    std::cout << "На работу алгоритма потрачено секунд "
        << static_cast<double>(finish - start) / CLOCKS_PER_SEC << std::endl;

    /*
    //Вывод простых чисел на консоль
    unsigned long long num = 0;
    for (const auto &flag : v)
    {
        if (flag)
        {
            // std::cout << num << " ";
        }
        ++num;
    }
    std::cout << std::endl;
    */
    
    system("pause");
    return 0;
}

Answer 3

int* parr = new int[n];

int* parr = new int[n+1];

А ещё, нерационально хранить в массиве сами числа. Числом является индекс, а массив можно сделать массивом bool'ов - тогда он будет занимать в 4 раза меньше места. Можно и до битов пожать, но тогда может на производительности сказаться.

БЛОГ НА HUSL

Ошибка при реализации решета Эратосфена на c++

Ответы (3 шт):