How to generate prime numbers upto 10^9?

general
,
1

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.
2

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

1 Like
3

ok what are these statements in the code smh

4

nice observation…

5

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

6

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

7

Which observation? I didn’t get it.