prime number : Sieve of Eratosthenes

import java.io.BufferedReader;
import java.io.InputStreamReader;

class test4 {

public static void main(String[] args)throws Exception {
    
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    int t = Integer.parseInt(br.readLine());
    
     int N = 1000000000;

    // initially assume all integers are prime
    boolean[] isPrime = new boolean[N+1];
    for (int i = 2; i <= N; i++) {
        isPrime[i] = true;
    }

    // mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i*i <= N; i++) {

        // if i is prime, then mark multiples of i as nonprime
        // suffices to consider mutiples i, i+1, ..., N/i
        if (isPrime[i]) {
            for (int j = i; i*j <= N; j++) {
                isPrime[i*j] = false;
            }
        }
    }
     isPrime[1] = false;
    while(t-->0)
    {
        
        String str[];
        str=br.readLine().split(" ");
        int m=Integer.parseInt(str[0]);
        int n=Integer.parseInt(str[1]);
        
        for(int i=m;i<=n;i++)
        {
            if(i%2==0&&i!=2)
            {
                continue;
            }
            if(isPrime[i])
            {
                System.out.println(i);
            }
        }
        
        
    }
    
    

}

}
i am getting the following error
Exception in thread “main” java.lang.OutOfMemoryError: Java heap space
in my net beans
and runtime error in code chef
on this line :boolean[] isPrime = new boolean[N+1];
how can i remove it or do i have to use different algorithm ??

@zargus : Why do you need to find all primes till 10^9 . This will not work . You may be able to find primes till 10^6 or 10^7 , but beyond that time and memory issues will come up .

Which problem are you trying to solve . Should be solvable without finding all primes till 10^9 .

10^9 is one GIGA .

1 Like

PRIME1 medium wanted to try it with sieve method actually !!

@zargus : Just generate primes till 40000 , they are enough to check primality of numbers till 10^9 . So when you have a test case , iterate through the values and check for primality . To generate primes till 40000 you can use the “sieve”.

1 Like

http://www.codechef.com/viewsolution/2355564

plzzzzzz can u check my solution i am getting wrong ansewer :frowning:

@zargus : Here is the corrected code for finding primes . I have changed only the first line or first loop

for (int i = 2; i <= N; i++) {

if (isPrime[i]) {

for (int j = i; i*j <= N; j++) {

isPrime[i*j] = false;

}

}

}

1 Like

The assumption we take when generating primes till only sqrt of a number is that if for a number n there is a factor which is greater than sqrt(n) then there has to be a factor which is less than n. Therefore to check for primality we check for numbers until the sqrt of n to see if it is a factor. If none of the numbers until then are factors then the number is indeed prime.

got it :slight_smile: thnx a lot