1

我编写了一个函数来使用 Eratosthenes 筛法处理素数。该函数使用整数可以正常工作，但我现在正在尝试实现对 long 的支持，以便我可以处理大数。

我似乎无法让函数与 long 一起使用，也看不出明显的原因。

错误是指来自类型转换等的典型精度警告，但我无法找出导致它们的原因：

   ./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

这是功能：

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

任何帮助将不胜感激！

4

2 回答 2

2

数组大小最大为 2^31-1，理论上是一个整数。你n+1的很长。所以这不匹配。您需要将n+1转换为整数：

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

现在，您知道了理论，您应该意识到long像这样为 s 实现筛子是行不通的，因为您将没有足够的内存，而 Java 根本不允许您制作大小大于 2^31 的数组-1。因此，只需将方法中的所有内容更改为int. 这看起来像这样：

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

为了优化大筛子的内存使用，我建议使用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;
}
于 2013-11-04T00:04:16.570 回答
0

我认为问题很简单：您应该对数组索引使用整数值（即方括号内的值）。

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;
}
于 2013-11-04T00:04:21.170 回答