Category: Codechef

Codechef : Prime Generator

Codechef Experience.

It is a medium scaled problem in Codechef. The task was to generate all prime numbers between two given numbers(M and N).

Constraints were N<=10^9  and N-M<=10^4.  Time:2 sec

Easy Part: We all know how we can tell whether any number is prime or not. By definition prime numbers are those numbers which have exactly 2 factors 1 and the number itself. 

There are many approaches to solve this problem.

Approach 1: We start with M and check whether it is divisible by any number between 2 and M-1. We do it until M==N.

Algo:

  1. read M,N
  2. if(m<=2) print 2 do m=m+1
  3. i=2
  4. check=( M%i)
  5. if(check ==0)   do  M=M+1 up-to(M<= N)  and   jump to step 3
  6. else do i=i+1  up-to (i<M) and  jump to step 4
  7. if(i==m) print M else M=M+1 up-to(M<=N) and jump to step 3

Time Complexity: (From wiki)

primes          approach
up to           takes

100             .00100 sec
1000            .02800 sec
10000           1.6980 sec
100000          130.44 sec
1000000         10732  sec

As this algo is taking bruteforce approach so it is impossible to solve the asked problem within the specified time.

Even if you try to make changes like don’t check an even number  ,increase i upto sqrt(i),and check primality of any number with only previous prime numbers,then also time complexity is very high.

Approach2:

Sieve of Eratosthenes 

It is a very standard approach and very fast . This algorithm was created by a Greek mathematician by the name of Eratosthenes.

Algo:

Simply make a list of consecutive numbers from 2 up to the number n. Now, take each number from the front of the list (first 2, then 3 and so on) and remove the multiples of each of these numbers from the rest of the list starting from the square of the number.  At the end of this procedure, all remaining numbers are prime.

The above picture(taken from the wiki) is showing the method to find the prime numbers upto 120.

So in this specific problem what i did is the following.

I took a Boolean array of size 40000 and initialize the with false. I start with i=2 and initialize the value at index 2*i with true.

then I increase i by 2 again and    initialize the value at index i with true.

Then do same thing with i=3,i=5,i=7… increasing every time  i with 3,5,7.. respectively.

Then doing such thing upto i=srt( 40000).If the value at any index  is false then that index is prime otherwise false.

When any number in the range [M,N]<=40000 i can check in O(1) time. If that number is greater than  40000 then i start with the index=2 and do the primality testing upto sqrt(any number) .

When i submit my solution I realized that this algorithm worked out to be very efficient.Why? Because  I saw this!!!!. 🙂