Prime number generation - SPOJ

Question

This is a program to generate prime numbers for a given range. The sieve of Eratosthenes algorithm was implemented, but still the SPOJ says time limit exceeded. Where can some optimizations be made?

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

import java.util.*;
import java.lang.*;
class Main
{
    public static void prime(int m, int n)
    {
    boolean arr[] = new boolean[n+1];
    for(int i = 0; i < arr.length; i++)
        arr[i] = true;
    for(int p = 2; p*p <= n; p++)
    {
        if(arr[p] == true)
        {
            for(int j = p*2; j <= n; j += p)
                arr[j] = false;
        }
    }
    for(int i = m; i <= n; i++) 
    { 
        if(arr[i] == true) 
            System.out.print(i + " "); 
    } 
}
public static void main (String[] args) throws java.lang.Exception
{
    Scanner in = new Scanner(System.in);
    int test = in.nextInt();
    int m = 0,n = 0,flag = 0;
    while(test > 0)
    {
        m = in.nextInt();
        n = in.nextInt();
        prime(m,n);
        test--;
    }
}
}

Answer 1

When generating prime numbers with the sieve of Eratosthenes, you can treat 2 as a special case. All other prime numbers are odd, so you can increment by 2:

for(int p = 3; p*p <= n; p += 2)

When you find a prime number \$p\$, you have already eliminated all multiples of prime numbers below \$p\$. This means starting at \$2p\$ and going up is eliminating already eliminated multiples. You can start at \$p^2\$, and since you are only concerned with odd numbers, go up multiples of \$2p\$

        for(int j = p*p; j <= n; j += 2*p)

When looping over the array for printing, you could again skip all even numbers, by going up by 2. But make sure you start on an odd number!

m |= 1;
for(int i = m; i <= n; i += 2) 

If you reversed your sense of the flag array, so true means "not prime", you wouldn't have to loop through the array to set all elements to true at the start. They would start off as false, which would mean "prime".

Marking all prime numbers on one pass, and then looping through your marked array printing out prime numbers is looping twice for possibly no reason. You can simply print out the prime numbers as you find them, if it is inside the required range. It would require some juggling, and optimization tricks to ensure you print out a number only when required, and only exactly once.

---

You generate the sieve 10 times, if you have 10 test cases. Maybe you could examine all 10 test cases, find the largest end point, and generate the sieve once???

Answer 2

The most time consuming part of the code is sieving prime numbers. And it is important to realize that each time you sieve, you'd arrive to the same set. In other words, you may compute it once - for the largest n - and reuse the result for all the tests.

There is at most 10 test cases. Read them, find the largest n, sieve the relevant primes, and then loop over the cases.

The sieve code is correct. The results are correct.