Реализация Решета Эратосфена

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

#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;

unsigned isqrt(unsigned value) {
  return static_cast<unsigned>(sqrt(static_cast<float>(value)));
}

int main()
{
    int t;
    cin >> t;
    long long * N;
    long long * M;
    long long n, m;
    N = new long long[t];
    M = new long long[t];
    for(int i = 0; i < t ; i++){
        cin >> M[i] >> N[i];
    }

    for(int i = 0; i < t ; i++){
        n = N[i];
        m = M[i];

        bool * A;
        A = new bool[n];
        if(A == 0)
        {
            cout << "Memory cannot be allocated";
            return 0;
        }

        for(int i=0;i < n;i++){
            A[i]=true;
        }
        A[0] = false;
        A[1] = false;

        unsigned sqrt = isqrt(n);
        for(int i = 2; i <= sqrt; i++)
        {
            if(A[i] == true){
                for(int j = i*i; j <= n; j = j + i)
                {
                    A[j] = false;
                }
            }
        }

        for(int i = m;i < n;i++)
        {
            if(A[i] == true )
                cout << i << "\n";
        }

        delete[] A;
    }

    delete[] M;
    delete[] N;
    return 0;
}

Программа аварийно завершает работу при больших значениях n и m (~10^16). Пожалуйста, помогите мне.


c++ sieve-of-eratosthenes
person Sumit Gera    schedule 12.04.2013    source источник
comment
Не вижу ни вопроса, ни проблемы/ошибки.   -  person    schedule 13.04.2013
comment
программа давит - не проблема?   -  person 4pie0    schedule 13.04.2013
comment
unsigned sqrt = isqrt(n) неправильно. пересчет сита для каждой входной пары является избыточным. он должен быть рассчитан только один раз.   -  person Will Ness    schedule 18.10.2015
comment
Вы понимаете, что даже высокооптимизированный многопоточный primesieve, который является версией решета Эратосфена, написанного на C , потребуется что-то порядка месяца, чтобы просеять простые числа до 10 ^ 16 на современном настольном компьютере? Этот код является открытым исходным кодом, поэтому вы можете его прочитать, но вы обнаружите, что он довольно сложен для выполнения того, что он делает. Вы обнаружите, что вам нужно написать сотни строк кода (и изучить множество методов и алгоритмов), чтобы приблизиться к этому.   -  person GordonBGood    schedule 09.05.2016
comment
Обратите также внимание, что для вычисления нескольких диапазонов простых чисел, как кажется, здесь вы намерены, не требуется просеивать весь диапазон простых чисел до верхнего простого индекса, а только до квадратного корня из верхнего простого индекса, затем используйте сегментированное сито для просеивания в нужном диапазоне, как и основное сито.   -  person GordonBGood    schedule 12.05.2016
comment
Наконец, вы не указываете, для какой цели вы собираетесь использовать этот огромный список простых чисел (до 10 ^ 16); если вам нужно знать только количество простых чисел до этого предела, сумму простых чисел до этого предела или наибольшее простое число, меньшее этого предела, существуют алгоритмы численного анализа, которые сократят время по сравнению с использованием сита из месяцев в минуты. Однако для нахождения максимальных промежутков между простыми числами или появления простых близнецов, троек и т. д. необходимо использовать сито.   -  person GordonBGood    schedule 15.05.2016

Ответы (4)


arrow_upward
4
arrow_downward 

for(int j = i*i; j <= n; j = j + i)
                   ^^

Если j == n, то A[j] = false будет присвоено элементу за концом массива. Тест должен быть j < n.

person John Kugelman    schedule 12.04.2013
comment
Но почему это происходит только при больших значениях m и n, а не при малых значениях? - person Sumit Gera; 13.04.2013
comment
@mozart Незаконный доступ к памяти вызывает неопределенное поведение в C ++. Результаты неопределенного поведения не обязательно предсказуемы. Это отличается от таких языков, как Java и Python, которые почти всегда дают предсказуемый и последовательный сбой. - person John Kugelman; 13.04.2013
comment
так стандартно, это должно быть запрещено - person 4pie0; 13.04.2013
comment
@cf16 cf16, если вы говорите, что недопустимые обращения должны каким-то образом перехватываться, вы упускаете одно из преимуществ C++ - не тратится время на проверку индекса перед каждым доступом. Если вам нужна такая поддержка, выберите другой язык и ожидайте, что он будет работать медленнее. - person Mark Ransom; 13.04.2013
comment
@MarkRansom: вы можете получить такую ​​поддержку в C++, если хотите. Например, использование std::vector с at() проверит все обращения. - person Jerry Coffin; 13.04.2013
comment
@MarkRansom Я просто пошутил, мне очень нравится нелегальный доступ : p - person 4pie0; 13.04.2013

arrow_upward
2
arrow_downward

Если вы собираетесь написать сито Эратосфена на C++, как насчет того, что вы действительно используете C++, а не пытаетесь относиться к нему как к какой-то сумасшедшей помеси C и языка ассемблера.

#include <vector>
#include <iostream>

unsigned long primes = 0;

int main() {
    int number = 10000000;
    std::vector<bool> sieve(number,false);
    sieve[0] = sieve[1] = true;

    for(int i = 2; i<number; i++) {
        if(!sieve[i]) {
            ++primes;
            for (int temp = 2*i; temp<number; temp += i)
                sieve[temp] = true;
        }
    }
    std::cout << "found: " << primes << " Primes\n";
    return 0;
}
person Jerry Coffin    schedule 12.04.2013
comment
В реализации этого нет проблем, но входные данные очень большие (~ 10 ^ 16), и поэтому я подумал об использовании указателей, а не vector. Шаблон вводит дополнительные накладные расходы, но я действительно узнал, что мне нужно реализовать сегментированное Решето Эратосфена для решения задачи. - person Sumit Gera; 14.04.2013
comment
@mozart: Как вы думаете, какие накладные расходы добавляет шаблон? [Подсказка: по крайней мере, обычно это делает скорее наоборот, сохраняя каждое логическое значение как один бит, тогда как ваше должно хранить каждое логическое значение как минимум в одном байте.] - person Jerry Coffin; 14.04.2013
comment
@SumitGera, если m ~ 10 ^ 16, то его sqrt равен ~ ...? Нет, для этой задачи вам не нужно сегментированное сито. Основное сито не расширяется; вы должны вычислить его только один раз, а затем просеять каждый из сегментов offset отдельно с основными простыми числами. - person Will Ness; 18.10.2015

arrow_upward
1
arrow_downward

Если n достаточно велико, чтобы вызвать ошибку выделения памяти, программа вылетит из-за неправильной обработки ошибки выделения памяти здесь

 A = new bool[n];
        if(A == 0)
        {
            cout << "Memory cannot be allocated";
            return 0;
        }

new не возвращает 0 в случае ошибки, а выдает std::bad_alloc, который не был перехвачен, что, в свою очередь, приведет к вызову неожиданного(), затем терминального() и, наконец, прерывания().
Правильная версия будет быть:

  try
  {
    A = new bool[n];
  }
  catch (std::bad_alloc& ba)
  {
    std::cerr << "Memory cannot be allocated: " << ba.what() << '\n';
  }
person alexrider    schedule 12.04.2013

arrow_upward
-1
arrow_downward

Запустите это в отладчике, чтобы определить, где произошел сбой, и отладьте оттуда. Скорее всего, это будет видно в этот момент.

Вы можете сделать это либо из IDE, либо из командной строки. В последнем случае скомпилируйте с помощью -g и запустите в такой программе, как gdb. Погуглите что-нибудь вроде "gdb шпаргалка" для начала.

person djechlin    schedule 12.04.2013
comment
Как SPOJ компилирует и запускает такие задачи? Это дает мне SIGABRT. Я не вижу причин для выполнения функции abort(). - person Sumit Gera; 13.04.2013
comment
@mozart Я не знаю, что такое SPOJ. - person djechlin; 13.04.2013