Sieve of Eratosthenes.

This post is about the Sieve of Eratosthenes. It's one of the very basic methods of calculating prime numbers quickly.

Skip the next 2 paragraphs if you don't want any context :p. For those who do here it is!

What's a prime number?
This is what google says- a number that is divisible by itself and 1.

Traditional Method of checking whether a number (n) is prime or not is by iterating through all the numbers from 2 to (n-1) and if we find that a particular number (x) in between divides the number then we say that the number is not a prime. This particular check takes O(n) {linear time as you need to check each number in between}.
Suppose you need to generate all the primes up to a given integer say N then you'll spend O(N) time to iterate through the loop and to check whether each number (n) in between is prime or not you'll have to spend O(n) time for each element.

Thus the total time is O(N^2). Much too expensive!! (Try plugging in large values of N and you'll see why!)

So how can we improve? Well here goes the very famous Sieve of Eratosthenes to find all the prime numbers under n-

Basic Logic of the Sieve: We start from 2 and proceed further for all numbers under n. For each number that we hit (which is 2 initially we strike of all it's further multiples as they cannot be prime 4,6..). All the numbers that we haven't stuck out at the end of this procedure will be prime. So basically this is how we proceed.

If a number has already been struck out I won't write it again. You'll see why later! ;) be with me.

Conclude 2 is prime. 4,6,8,10....are not.
Conclude 3 is prime. 9,15,21...are not.(6,12,18 were already struck out because of 2).
Conclude 5 is prime 25,35....are not.
Continue this process till we have only prime numbers left under n.

Now as to why I didn't write the numbers that were already struck out- If you observe that the first multiple of each prime number that is to be struck out is that square of the number. We''ll use this in our code :). You can also mathematically prove this. Conversely we'll also only strike out multiples of numbers that are under sqrt(n) as the ones larger than it will be the prime numbers left which have no multiples under n.

Coding Part:

Input: n-the number under which we need to print all the prime numbers.
Output: all the prime numbers under n

Logic: We will initially have an array (array) of n size and fill all the elements of it with a default value. (Suppose 1 for int data type, true boolean type). Then we'll iterate (i) from 2 to square root of n. For each index i we'll check whether array[i] will be 1 or not. If it is 1 then for all its multiples under n we make array[multiple]=0 starting from the square of the number(i*i). Array elements with indices 1 at the end of this procedure will be prime.

Code In C++:
#include <iostream>
#include <cmath>
int main()
{
 std::cout<<"Enter the number till which you want to generate primes"<<std::endl;
 int n;
 std::cin>>n;
 int *array; //my way of declaring an array. You can also int array[n]
 array=new int[n];
 for(int i=0;i<n;i++) //make all array[i]=1
  array[i]=1;
 for(int i=2;i<sqrt(n);i++) //iterating form one to sqrt(n)
 {
  int counter=0;
  if(array[i]==1)
  {
   for(int j=i*i;j<n;j=i*i+counter*i) //marking all the multiples of i (=0) starting from
   {                                                      //i*i
    array[j]=0;
    counter++;
   }
  }
 }
        for(int i=2;i<n;i++) //printing out all the primes.
 {
  if(array[i]==1)
   std::cout<<i<<" ";
 }
 std::cout<<std::endl;
 return 0;
}

Guys I won't always be coding in 2 languages :p. This one is only because I've implemented it in both.

Code in Java:
import java.io.*;
import java.util.Arrays;
class primeGenerator
{
 public static void main(String [] args)throws IOException
 {
  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  System.out.println("Enter the number till which you want to generate primes?");
  int n=Integer.parseInt(br.readLine());
  Boolean[] array=new Boolean[n];
  Arrays.fill(array,Boolean.TRUE); //make all array[i]=true
  for(int i=2;i<Math.sqrt(n);i++) //iterating form one to sqrt(n)
  {
   if(array[i]==true)
   {
    int counter=0;
    for(int j=i*i;j<n;j=i*i+counter*i) //marking all the multiples of i (=0) starting
    {                                                      //from i*i
     array[j]=false;
     counter++;
    }
   }
  }
  for(int i=0;i<n;i++) //printing out all the primes.
  {
   if(array[i]==true)
   {
    System.out.print(i+" ");
   }
  }
  System.out.println();
 }
}

Hope this Helps! Sieve of Eratosthenes is used in a lot of Competitive Coding Questions and I've personally used it in many questions.

There is however a better method so to speak which is the segmented sieve. You use it when you need to have less space and also when you need to generate primes between two given numbers and not under a given number like we do in the Sieve of Eratosthenes. I'll blog about it too some time :D.

Stay Tuned!!