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--;
}
}
}
m, n
ranges? \$\endgroup\$2
to ensurearr[0]
andarr[1]
arefalse
. \$\endgroup\$