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

just eratosthenes sieve should be enough.

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

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]<<" ";
}
}
```

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