Code - Sieve of Eratosthenes
Sieve of Eratosthenes is an efficient way to precompute primes up to a number.
Classic Sieve
bool is_composite[N];
vector<int> primes;
for(int i=2; i<N; i++)
{
if(!is_composite[i])
{
primes.push_back(i);
// mark multiples of i as composite
for(int j=2*i; j<N; j+=i) is_composite[j] = 1;
}
}Linear Sieve
int lp[N]; // stores the lowest prime factor of numbers
vector<int> primes;
for(int i=2; i<N; i++)
{
if(!lp[i])
{
// If a number doesn't have a lower prime factor, it is prime
lp[i]=i;
primes.push_back(i);
}
for(int j=0; j<primes.size() && primes[j]<=lp[i] && i*primes[j]<N; j++) lp[i*primes[j]] = primes[j];
}