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.

kodeknight prime

See also