# prime number : Sieve of Eratosthenes

class test4 {

``````public static void main(String[] args)throws Exception {

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[];
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

@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 thnx a lot

//