Как я могу напечатать простые числа до 10 ^ 8 с помощью Sieve? - PullRequest
Новая
       48

Как я могу напечатать простые числа до 10 ^ 8 с помощью Sieve?

0 голосов
/ 04 августа 2020

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

#include <iostream>
#include <vector>
//#define MAX 10000
typedef long long int ll;
using namespace std;
vector <ll> primes;
void sieve(){
    ll MAX = 100000000;
    bool isPrime [MAX];
    for(ll i = 0;i < MAX; ++i)isPrime[i] = true;
    //isPrime[0] = isPrime[1] = false;
    
    for(ll i=3; i*i <= MAX; i += 2){
        if(isPrime[i]){
            for(ll j = i*i; j <= MAX; j += i){
                isPrime[j] = false;
            }
        }
    }
    primes.push_back(2);
    for(ll i = 3; i <= MAX; i += 2){
        if(isPrime[i]){
            primes.push_back(i);
        }
    }
    for(ll i = 0; i <= 10; ++i){
        cout<<primes[i]<<endl;
    }
}
int main(){
    sieve();
    return 0;
}

1 Ответ

2 голосов
/ 04 августа 2020

Вы создаете статический c массив размером 10^8, который хранится в стеке. Это слишком велико для стека и, вероятно, вызовет переполнение стека.

Вместо этого используйте vector, который хранит данные в куче, например: 

vector<bool> isPrime(MAX+1);

Вот a demo .

Также обратите внимание, что у вас есть ошибка на одну ошибку, поскольку вы индексируете по индексу MAX, поэтому вектор должен иметь размер MAX+1.

Также вам следует избегать using namespace std;, а также typedefs, таких как ll, они затрудняют чтение кода.

...