Below is my implementation for finding all primes less than 1e6. But for some reason, I get a WA with this code. Is something wrong here?
set<int> prime;
prime.insert(2);
prime.insert(3);
for(int i = 6; i < 1e6 + 7; i+=6)
{
prime.insert(i - 1);
prime.insert(i + 1);
}
If it’s wrong, what is the best method to do this?
[EDIT] Apart from Seive of Eratosthenes.
1 Like
I don’t think this will be true for every i. I think seive is the best method. eg 35 and 37
Clearly, it doesn’t work when i=24, as i+1=25
which isn’t a prime number. 
1 Like
Sieve of Eratosthenes is the best way.
Time complexity is O(nloglogn)
space complexity is O(n)
Right. So every prime number if of the form 6n + 1 or 6n - 1, but not the other way round.
1 Like
Go through the first answer here maths
1 Like
Sieve of Sundaram is the best one for finding and print all prime number less than N
1 Like
what is the complexity of Sieve of sundaram…Instead of this u can use Sieve of Eratosthenes (Nloglogn) or linear sieve (N) or wheel factorisation (N/loglogN) …
Use linear sieve
(I don’t know how complexity is O(N) but yeah it’s better )
bool composite[MAX+1];
vi primes;
void LinearSieve(){
//0 means prime , 1 means non prime
memset(composite,0,sizeof(composite));
for(int i=2;i<=MAX;i++)
{
if(!composite[i])
primes.push_back(i);
for(int j = 0 ; j < sz(primes) and i*primes[j] <= MAX; j++)
{
composite[primes[j]*i]=1;
if(i%primes[j]==0)break;
}
}
}
Yeah, this is what I ended up using. This should be O(n\text{log }n).
Yes my bad. It’s O(n log(log(n))).
yeah it’s for sieve of Eratosthenes 
1 Like
I didn’t know about linear Sieve. Thanks!
1 Like
Instead of taking int array , use bool array , to find out whether a number is prime or not , in case of sieve of eratosthenes … it is fast and efficient and u can make array of bool upto 108
bool prime[MAX+1];
void sieve1(){ //prime or not
for(int i=0;i<=MAX;i++) prime[i]=1;
prime[0]=prime[1]=0;
for(lli i=4;i<=MAX;i+=2) prime[i]=0;
for (int p=3; p*p<=MAX; p+=2){
if (prime[p] == 1)
for (int i=p*2; i<=MAX; i += p){
prime[i] = 0;
}
}
}
2 Likes
Thanks! I’m not very comfortable with questions involving number of divisors and prime number checks. Hope this helps with that. 
1 Like
Every prime number greater than 3 is of the form 6n+1 or 6n-1. The converse is not true. Use sieve of Eratosthenes or just modify your code a bit.
Add a check prime function. We assume that n > 3.
bool isPrime(int n)
{
bool flag = 1;
for (int i = 2; i*i <= n; ++i)
{
if (n % i == 0)
{
flag = 0;
break;
}
}
return flag;
}
set <int> prime;
prime.insert(2);
prime.insert(3);
for(int i = 6; i < 1e6 + 7; i+=6)
{
if (isPrime(i-1)) prime.insert(i - 1);
if (isPrime(i+1)) prime.insert(i + 1);
}
The complexity will be O(n(\sqrt{n}+\log{n})) because isPrime()
is O(\sqrt{n}) and insertion in a set takes O(\log{n}) but sieve of Eratosthenes is only O(n\log{(\log{n})}) which is much more fast.
I’d suggest using sieve rather than this approach (or remove the set and use a vector with push_back()
).
1 Like
Thanks! I had used a set because that was within limits. Anyways the best thing to do is a bool array, with O(1) lookup, I guess.
1 Like