0
\$\begingroup\$

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--;
    }
}
}
\$\endgroup\$
6
  • \$\begingroup\$ Please add the restrictions. How many test cases? What are the m, n ranges? \$\endgroup\$
    – vnp
    Oct 1, 2018 at 4:15
  • \$\begingroup\$ Constraints added \$\endgroup\$
    – Sridhar Cr
    Oct 1, 2018 at 5:23
  • \$\begingroup\$ Bug: 1 is not a prime number. You should start your initialization loop at 2 to ensure arr[0] and arr[1] are false. \$\endgroup\$
    – AJNeufeld
    Oct 1, 2018 at 5:45
  • \$\begingroup\$ Related, related. Some of the comments on those earlier attempts at the same problem may not be applicable to this code, but I mention them also for future searchers whose code they may apply to. \$\endgroup\$ Oct 1, 2018 at 8:57
  • \$\begingroup\$ There is at least 1 Prime generation task on SPOJ that requires to use cache aware C/C++ code and time limits are so tight it is impossible to do it in Java/most other languages. \$\endgroup\$
    – user158037
    Oct 1, 2018 at 10:12

2 Answers 2

1
\$\begingroup\$

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???

\$\endgroup\$
0
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.