To find the list of primes till N

Problem

Given a number n, print all primes smaller than or equal to n.

Example
For example, if n is 10, the output should be “2, 3, 5, 7″. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19″.

Solution

Method 1 - Brute force
We just loop till number N, and check if individual iterator is prime or not.

Code :

void printPrimeTillN(int n)
{
    for(i=2;i<=n;i++)
    {
        for(j=2;j<=i-1;j++)
     if(i%j==0)
  break;
         
        if(i==j)
  print (i);
         
    }
}

We can simply write this as :

void printPrimeTillN(int n)
{
    for(i=2;i<=n;i++)
    {
        if(checkIfPrime(i))
           print(i);         
    }
}

We know couple of primality tests discussed here. So, in nested loop, we can interate till i/2 or sqrt(i) or we can use any other method.

Method 2 - Sieve of Eratosthenes
We have discussed the  method here.

Method 3 - Sieve of Atkins
 We have discussed this method here.

Please share if you some other method.

Thanks.