How to get table size 2^32 in java

Question

I have to get in java protected final static int [] SIEVE = new int [ 1 << 32 ]; But i cant force java to that.

Max sieve what i get is 2^26 i need 2^32 to end my homework. I tried with mask but i need to have SIEVE[n] = k where min{k: k|n & k >2}.

EDIT I need to find Factor numbers from 2 to 2^63-1 using Sieve and sieve must have information that P[n]= is smallest prime with divide n. I know that with sieve i can Factorise number to 2^52. But how do that exercises with holding on to the content.

EDIT x2 problem solved

Answer 1

If you really need to store that much data in memory, try using java.util.LinkedList collection instead.

However, there's a fundamental flaw in your algorithm if you need to store 16GB of data in memory. If you're talking about Sieve of Eratosthenes and you need to store all primes < 2^32 in an array, you still wouldn't need an array of size 2^32. I'd suggest you use java.util.BitSet to find the primes and either iterate and print or store them in a LinkedList as required.

Answer 2

You can't. A Java array can have at most 2^31 - 1 elements because the size of an array has to fit in a signed 32-bit integer.

This applies whether you run on a 32 bit or 64 bit JVM.

---

I suspect that you are missing something in your homework. Is the requirement to be able to find all primes less than 2^32 or something? If that is the case, they expect you to treat each int of the int[] as an array of 32 bits. And you need an array of only 2^25 ints to do that ... if my arithmetic is right.

A BitSet is another good alternative.

A LinkedList<Integer> is a poor alternative. It uses roughly 8 times the memory that an array of the same size would, and the performance of get(int) is going to be horribly slow for a long list ... assuming that you use it in the obvious fashion.

If you want something that can efficiently use as much memory as you can configure your JVM to use, then you should use an int[][] i.e. an array of arrays of integers, with the int[] instances being as large as you can make them.

---

I need to find Factor numbers from 2 to 2^63-1 using Sieve and sieve must have information that P[n]= is smallest prime with divide n. I know that with sieve i can Factorise number to 2^52. But how do that exercises with holding on to the content.

I'm not really sure I understand you. To factorize a number in the region of 2^64, you only need prime numbers up to 2^32 ... not 2^52. (The square root of 2^64 is 2^32 and a non-prime number must have a prime factor that is less than or equal to its square root.)

It sounds like you are trying to sieve more numbers than you need to.