# How to generate prime numbers upto 10^9?

I was trying to solve this problem Prime Generator. In this problem, I have to generate prime numbers up to 10^9. I am using Sieve of Eratosthenes but it is taking quite long. How to optimize this or is there any other theory?

Here is my code, that I have implemented:-

``````#include<bits/stdc++.h>
typedef long long ll;
#define MAX 1000000000
using namespace std;
int main() {
bool *primes = new bool[MAX+1];
for(ll i =0; i<MAX+1; i++) {
primes[i] = true;
}
ll sqr = sqrt(MAX);
primes[0] = false;
primes[1] = false;
for(ll p=2; p<=sqr; p++){
if(primes[p]) {
for(ll i = p*p; i<=MAX; i+=p) {
primes[i] = false;
}
}
}
cout<<"prime numbers done";
int t;
cin>>t;
while(t--){
ll m, n;
cin>>m>>n;
for(ll i = m; i<=n; i++) {
if(primes[i]){
cout<<i<<" ";
}
}
}
return 0;
}

I am trying to calculate all primes numbers and then answer the queries.
``````

Use Segmented Sieve, basically, instead of creating a Sieve of size `n`, we create a Sieve of only size `sqrt{n}`.

1 Like

ok what are these statements in the code smh

nice observationâ€¦

Actually, this code was taking a long time. So just to debug this, I wrote a statement to know that primes are calculated.

Okay, I will read about it. Till now, I only knew about Naive method and Sieve of Erathonense.

Which observation? I didnâ€™t get it.