CODEWITHSUNDEEP
c++algorithmnumberssieve-of-eratosthenes
Fahim Hassan
Fahim Hassan

Reputation: 71

How can I print prime numbers till 10^8 using Sieve?

I have recently learnt Sieve algorithm and started to play with it to learn how to use the algorithm in problems. I have written the code correctly as I can't find any bugs in it, but it closes without showing any output. Can't find what's wrong. Help would be appreciated.

#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;
}

Upvotes: 0

Views: 194

Answers (1)

cigien
cigien

Reputation: 60238

You are creating a static array of size 10^8, which is stored on the stack. This is too large for the stack, and will likely cause a stack overflow.

Instead, use a vector that stores the data on the heap, like this:

vector<bool> isPrime(MAX+1);

Here's a demo.

Also, note that you have an off by one error, since you are indexing at the index MAX, so the vector should be size MAX+1.

Also, you should avoid using namespace std;, as well as typedefs like ll, they make the code harder to read.

Upvotes: 2

Related Questions