Sieve Of Eratosthenes – Primality testing for numbers in a range

If u want to generate a list of all the primes in the range "1 to n" then a very simple to code algorithm which u can use is Sieve Of Eratosthenes.

The sieve algorithm explained in simple words is:
1) Mark all numbers in the range as prime.
2) Mark 1 to be trivially not prime
3) Mark even numbers (except two) to be trivially not prime.
4) Start from i = 3 (next number which is marked true) and mark all its multiples from i*i to n as not prime.
5) Continue no. 4 for all i till sqrt(n).

bool flag[n+1];
memset(flag, true, sizeof flag);
flag[1] = false;
for(int i=4; i <= n; i+=2)
 flag[i] = false;
for(int i=3; i <= sqrt(n); i+=2)
{
  if(flag[i])
    for(int j=i*i; j<=n; j += i)
      flag[j] = false;
}

Complexity of the algorithm is O(n log log n) in terms of arithmetic operations.

Now, you can use this base table to solve a wide variety of problems involving prime numbers.

Practice Problem:
PRIME1