How to solve this problem

Can anyone help me in this problem? I am getting runtime error. Do I need to use segmented sieve. Can anyone help in this solution with code?


just eratosthenes sieve should be enough.

Share your code in case you can’t make it work

Here is my code-

 using namespace std;
   vector<int>SieveOfEratosthenes(int n) 
     bool prime[n+1]; 
     memset(prime, true, sizeof(prime)); 
      for (int p=2; p*p<=n; p++) 
         if (prime[p] == true) 
             for (int i=p*p; i<=n; i += p) 
                 prime[i] = false; 
    for (int p=2; p<=n; p++){ 
        if (prime[p]){
     return primes;
 int main(){
 	int n;
 	for(int i=0;i<n;i++){
 		cout<<v[i]<<" ";

if you want first 1e6 primes you should get primes up to 2E7 approx, if you check up to n=1E6 you will get only 78498 primes

1 Like

you can speed up the algo if you replace your inner for loop like this

for (int i=p*p; i<=n; i += 2*p)

and of course there’s no need to scan even numbers (except 2) in outer loops

1 Like

So, I need to only change the limit to 2e7? I tried this just now, still its runtime error. Can you please check.

now it’s because of some limitation in ideone, I do not know the limits, try it here in codechef, I tried it and worked

1 Like

Yes it worked. Thank you @carre

1 Like