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.
- read M,N
- if(m<=2) print 2 do m=m+1
- check=( M%i)
- if(check ==0) do M=M+1 up-to(M<= N) and jump to step 3
- else do i=i+1 up-to (i<M) and jump to step 4
- 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.
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.
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!!!!. 🙂