# Find all primes less than N

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

N(log(logn)) ?

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