finding prime numbers less than a LONG number using sieve

Question

I have to find number of prime numbers less than or equal to a given number n. I am using Sieve of Eratosthenes for finding primes.

This is the code I've written:

static int find_prime(int n) {
    boolean[] arr = new boolean[n+1];
    Arrays.fill(arr, true);

for(int i=2;i<=n;i++) {
    if(arr[i]==true) {
        for(int j=2*i; j<=n; j+=i)
            arr[j] = false;
    }
}
int count=0;
for(int i=2;i<=n;i++) {
    //System.out.print(arr[i]+" ");
    if (arr[i] == true)
        count++;
    }
    return count;
}

This code works well for integer values, but I have to implement it for long numbers. And Java doesn't allow creating long size array so boolean[] arr = new boolean[n+1]; doesn't work. Can someone suggest me a way to solve this?

Possible duplicate of [Java array with more than 4gb elements](http://stackoverflow.com/questions/878309/java-array-with-more-than-4gb-elements) — azurefrog, Aug 11 '16 at 14:34
You've already purchased 10 [Exabytes](http://www.whatsabyte.com/) of memory for your sieve, right? — Sergey Kalinichenko, Aug 11 '16 at 14:36
There are more space-efficient ways to store a sequence of booleans. A bit field, for example. Also, you don't really have to represent even numbers in the sieve. — khelwood, Aug 11 '16 at 14:38
@dasblinkenlight you can suggest me a better way to find the answer. — Krishh, Aug 11 '16 at 14:43
@khelwood is there a better way for doing this other than sieve? — Krishh, Aug 11 '16 at 14:46
You can write a sieve without using a boolean array. https://en.wikipedia.org/wiki/Bit_array — khelwood, Aug 11 '16 at 14:50
@khelwood This would take him to 2^36 - a great deal of an improvement on 2^31, but still quite a bit short of 2^63 that he is trying to achieve. — Sergey Kalinichenko, Aug 11 '16 at 14:59
@dasblinkenlight I make it 2^37 if you use an array of longs, but I see your point. — khelwood, Aug 11 '16 at 15:07
@khelwood I was off by 1, it's 2^37, not 2^36. 64 is 2^6, and the max array size is 2^31, so you can store up to 2^(6+31) bits. Skipping even numbers brings you up to 2^38. — Sergey Kalinichenko, Aug 11 '16 at 15:11
You might be interested in a [segmented sieve](http://stackoverflow.com/a/10249801/448810). — user448810, Aug 11 '16 at 20:24
simple [search](http://stackoverflow.com/search?tab=relevance&q=%5bjava%5d%20%5bprimes%5d%20is%3aa) gives you [this answer](http://stackoverflow.com/questions/9625663/calculating-and-printing-the-nth-prime-number/9704912?s=1|8.7171#9704912). — Will Ness, Aug 12 '16 at 16:42

score 2 · Accepted Answer · answered Aug 11 '16 at 14:51

You wouldn't have enough memory to represent the entire sieve, because it is in exabytes. Even BitSet is not going to fit all the indexes that you need, because ultimately it uses an array of longs to store the bits.

You can find your answer with a mixed approach:

Build and run a sieve up to Integer.MAX_VALUE
Harvest primes up to Integer.MAX_VALUE into an array of longs
Observe that you can stop checking for divisors upon reaching square root of candidate number c
This means that you already have all potential divisors for values above Integer.MAX_VALUE
Use array of divisors to filter numbers between Integer.MAX_VALUE and n

Since you do not need to store additional primes after Integer.MAX_VALUE, your code would not run out of memory.

Thank you for mentioning that BitSet doesn't reduce the memory requirement enough. If I figured this right, it would still require as much as 2^60 bytes of memory. I don't believe current common desktop processors can address that much. — Fred Larson, Aug 11 '16 at 14:58

finding prime numbers less than a LONG number using sieve

1 Answers1