Return to 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. Please provide some optimizations.

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--;
    }
}
}

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--;
    }
}
}

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. Please provide some optimizations.

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--;
    }
}
}

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. Please provide some optimizations.

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--;
    }
}
}