Java data-type issue

Question

I have written a function to work on prime numbers using the sieve of Eratosthenes method. The function works fine using integers but I am now trying to implement support for long so that I can work with large numbers.

I cannot seem to get the function working with longs and can't see an obvious reason why.

Errors refer to the typical precision warning from typecasting etc but I cannot work out what's causing them:

   ./com/wkilgour/lang/Maths.java:21: error: possible loss of precision
        boolean[] isPrime = new boolean[n + 1];
                                          ^
  required: int
  found:    long
./com/wkilgour/lang/Maths.java:24: error: possible loss of precision
            isPrime[i] = true;
                    ^
  required: int
  found:    long
./com/wkilgour/lang/Maths.java:27: error: possible loss of precision
            if (isPrime[i])
                        ^
  required: int
  found:    long
./com/wkilgour/lang/Maths.java:29: error: possible loss of precision
                    isPrime[i * j] = false;
                              ^
  required: int
  found:    long
4 errors

Here is the function:

public static boolean[] primeSieve(long n)
{
    boolean[] isPrime = new boolean[n + 1];

    for (long i = 2L; i <= n; i++)
        isPrime[i] = true;

    for (long i = 2L; i*i <= n; i++)
        if (isPrime[i])
            for (long j = i; i*j <= n; j++)
                isPrime[i * j] = false;

    return isPrime;
}

Any help would be greatly appreciated!

Yes there's a few errors relating to the precision. I've added the full error now — Wesk, Nov 04 '13 at 00:04
Have you thought about how much memory you'll need, to know the primeness of numbers up to `long` values? — Dawood ibn Kareem, Nov 04 '13 at 00:09
Use a segmented sieve, where you split the sieve into smaller parts. http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes — starblue, Nov 04 '13 at 07:13

Martijn Courteaux · Accepted Answer · 2013-11-04T00:09:43.157

Array size is maximum 2^31-1, in theory, which is an integer. Your n+1 is a long. So that doesn't match. You will need to cast the n+1 to an integer:

boolean[] isPrime = new boolean[(int) (n + 1)];

Now, you know the theory, you should realize that implementing a sieve for longs like this isn't going to work, since you will not have enough memory and Java simply doesn't allow you to make arrays of sizes bigger than 2^31-1. So, just change everything in your method to int. This would look like this:

public static boolean[] primeSieve(int n)
{
    boolean[] isPrime = new boolean[n + 1];

    for (int i = 2; i <= n; i++)
        isPrime[i] = true;

    for (int i = 2; i*i <= n; i++)
        if (isPrime[i])
            for (int j = i; i*j <= n; j++)
                isPrime[i * j] = false;

    return isPrime;
}

And to optimize the memory usage for big sieves, I'd recommend using a java.util.BitSet:

public static BitSet primeSieve(int n)
{
    BitSet isPrime = new BitSet(n+1);

    for (int i = 2; i <= n; i++)
        isPrime.set(i);

    for (int i = 2; i*i <= n; i++)
        if (isPrime.get(i))
            for (int j = i; i*j <= n; j++)
                isPrime.set(i * j, false);

    return isPrime;
}

This is the code that I had originally which worked perfectly. I'm trying to use much larger numbers than integers though which is why I wanted to add long support — Wesk, Nov 04 '13 at 00:09
Your best bet is to use BitSet, but this still won't allow you to implement the algo for longs, because even BitSet accepts only 2^31-1 bits. Creating a BitSet with `2^31-1` bits would use 2 GiB of ram. While doing the same with a `boolean[]` array, it would take 16 GiB of ram. — Martijn Courteaux, Nov 04 '13 at 00:11

score 0 · Answer 2 · answered Nov 04 '13 at 00:04

I think the problem is simple: you should use an integer value for an array index (i.e. the values within square brackets).

public static boolean[] primeSieve(long n)
{
    boolean[] isPrime = new boolean[(int) (n + 1)];

    for (long i = 2L; i <= n; i++)
        isPrime[(int) i] = true;

    for (long i = 2L; i*i <= n; i++)
        if (isPrime[(int) i])
            for (long j = i; i*j <= n; j++)
                isPrime[(int) (i * j)] = false;

    return isPrime;
}

Java data-type issue

2 Answers2