How to solve this problem

general
, ,
1

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?

2 Likes
2

just eratosthenes sieve should be enough.

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

3

Here is my code-

 #include<bits/stdc++.h>
 using namespace std;
 
   vector<int>SieveOfEratosthenes(int n) 
 { 
 	vector<int>primes;
     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]){
 		   primes.push_back(p);
 	   }
 	}
     return primes;
 }
 int main(){
 	vector<int>v=SieveOfEratosthenes(1000000);
 	int n;
	cin>>n;
 	for(int i=0;i<n;i++){
 		cout<<v[i]<<" ";
 	}
 }
4

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
5

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
6

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

7

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
8

Yes it worked. Thank you @carre

1 Like