Starting from today, I am trying to solve 2 problems from SPOJ, if not I will try to describe the thought process of solving it. Today I picked up the first problem as PRIME1.

The problem is about generating the prime numbers in the given ranges. We can solve it in brute force approach, but if you see the constraints of the input, you don’t think about brute force.

The constraints is: 1 <= m <= n <= 1000000000, n-m<=100000

So the classical method is to use “sieve of eratosthenes “,  but using this will result in “Time limit exceeded”. So we have to tweak the original algorithm to find the primes in the range which is called as “segmented sieve of eratosthenes”. Pseudo code is as follows:

we have to find prime numbers in the range (n, m) where n<m;

1)Initialize arr[m-n] to zero

1)Find all primes from 2 to Sqrt(m) using classical sieve of eratosthenes and store in primes[]

2)for each prime number in primes[], find lowerlimit using (n/prime[i])*prime[i] which gives nearest number to n and divisible by prime[i]. And then mark all the numbers as not prime(by assigning 1) from lowerlimit to m by increment of  lowerlimit + prime[i]

3)the indices of arr whose values are zero are prime.

You find the solution for this at https://github.com/bharaththiruveedula/Algorithms/blob/master/SPOJ/PRIME1_sse.java

And there is one more and easier approach for this, it is self explanatory you can find the code at https://github.com/bharaththiruveedula/Algorithms/blob/master/SPOJ/PRIME1.java

Advertisements