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!

Answer 1

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;
}

Answer 2

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;
}