埃拉托斯特尼筛问题：处理非常大的数字

Question

我正在使用埃拉托斯特尼筛法求解 Sphere 的在线法官 素数生成器。

我的代码适用于提供的测试用例。 但是..正如问题明确指出的那样：

输入以数字 t 开头 测试用例在一行中（t<=10）。 在接下来的每一行中都有 两个数字 m 和 n (1 <= m <= n <= 1000000000, nm<=100000) 分隔 一个空格。

我知道方法 Integer.parseInt() 在处理非常大的数字时会抛出异常，并且在线判断表明正在抛出异常，因此我更改了 parseInt 的每个情况 code> 到我的代码中的 parseLong 。

嗯，事情在 Netbeans 6.5 上运行良好，m 和 n 的值很小。

package sphere;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{

public static void runEratosthenesSieve(long lowerBound, long upperBound) {

      long upperBoundSquareRoot = (long) Math.sqrt(upperBound);

      boolean[] isComposite = new boolean[(int)upperBound + 1];

      for (int m = 2 /*int m = lowerBound*/; m <= upperBoundSquareRoot; m++) {

            if (!isComposite[m]) {

                if (m>=lowerBound) {System.out.println(m);}

                  for (int k = m * m; k <= upperBound; k += m)

                        isComposite[k] = true;

            }

      }

      for (int m = (int)upperBoundSquareRoot; m <= upperBound; m++)

            if (!isComposite[m])

                 if (m>=lowerBound){ System.out.println(m);}

}

public static void main(String args[]) throws java.lang.Exception{

       BufferedReader r = new BufferedReader(new InputStreamReader(System.in));


       String l = r.readLine();

       int testCases = Integer.parseInt(l); 

       for (int i =0; i<testCases; i++){
       String s =r.readLine();

       String []splitted=s.split(" ");


       long lowerBound = Long.parseLong (splitted[0]);
       long upperBound = Long.parseLong(splitted[1]);

       runEratosthenesSieve (lowerBound,upperBound);

       System.out.println("");
       }
}

}

输入+输出：

run:
2
1 10
2
3
3
5
7

3 5
3
5

BUILD SUCCESSFUL (total time: 11 seconds)

但是 JCreator LE 是这样说的：

2
1 10
Exception in thread "main" java.lang.NumberFormatException: For input string: ""
    at java.lang.NumberFormatException.forInputString(NumberFormatException.java:48)
    at java.lang.Long.parseLong(Long.java:424)
    at java.lang.Long.parseLong(Long.java:461)
    at sphere.Main.main(Main.java:51)

Process completed.

这里我没有整数溢出，但是为什么 jcreator 会抱怨呢？

考虑到边界测试用例，程序在 Netbeans 上也会崩溃：

run:
2
999900000 1000000000 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at sphere.Main.runEratosthenesSieve(Main.java:13)
        at sphere.Main.main(Main.java:55)
Java Result: 1

我该如何处理问题陈述中那些巨大的整数？

编辑：根据建议，我更改了 BitSet 的布尔数组，但仍然收到 OutOFMemoryError：

package sphere;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.BitSet;

public class Main{

public static void runEratosthenesSieve(long lowerBound, long upperBound) {

      long upperBoundSquareRoot = (long) Math.sqrt(upperBound);

      //boolean[] isComposite = new boolean[(int)upperBound + 1];

      BitSet isComposite = new BitSet((int)upperBound+1);

      for (int m = 2 /*int m = lowerBound*/; m <= upperBoundSquareRoot; m++) {

            if (!isComposite.get(m)) {

                if (m>=lowerBound) {System.out.println(m);}

                  for (int k = m * m; k <= upperBound; k += m)

                        isComposite.set(m);

            }

      }

      for (int m = (int)upperBoundSquareRoot; m <= upperBound; m++)

            if (!isComposite.get(m))

                 if (m>=lowerBound){ System.out.println(m);}

}

public static void main(String args[]) throws java.lang.Exception{

       BufferedReader r = new BufferedReader(new InputStreamReader(System.in));


       String l = r.readLine();

       int testCases = Integer.parseInt(l); 

       for (int i =0; i<testCases; i++){
       String s =r.readLine();

       String []splitted=s.split(" ");


       long lowerBound = Long.parseLong (splitted[0]);
       long upperBound = Long.parseLong(splitted[1]);

       runEratosthenesSieve (lowerBound,upperBound);

       System.out.println("");
       }
}

}

输入输出：

run:
1
999900000 1000000000
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.BitSet.initWords(BitSet.java:144)
        at java.util.BitSet.<init>(BitSet.java:139)
        at sphere.Main.runEratosthenesSieve(Main.java:16)
        at sphere.Main.main(Main.java:58)
Java Result: 1
BUILD SUCCESSFUL (total time: 14 seconds)

Answer 1

这是你的问题：

boolean[] isComposite = new boolean[(int)upperBound + 1];

这将使用大量的空间，因为它为每个布尔值分配 4 个字节以允许更快的访问。 使用 java.lang.BitSet 来避免那。

最终，您的数字也可能会变得太大，并且您将不得不使用 BigInteger。 但到那时，埃拉托斯特尼的筛子可能也不再适用了。

Answer 2

您使用了大量空间来存储布尔值。 您可能会尝试将每个布尔值压缩为一位。 想想看，您真的需要为下限和上限之间的每个数字提供一个布尔值吗？ 例如，偶数永远不是质数（2 除外），也不是 3 的倍数（3 除外）等。 此页面可能会给您一些好主意。

Answer 3

您的 BitSet 实现中有一个小错误。 该行：

                    isComposite.set(m);

实际上应该是：

                    isComposite.set(k);

修复该行后，代码在测试用例 999900000 到 1000000000 上运行没有错误，吐出以 999900017 开头并以 999999937 结尾的 4,832 个素数。 BitSet 使用了 125 MB 内存，该方法占用了 17在我的 2.2 GHz 笔记本电脑上运行几秒钟。

Answer 4

您使用 BigInteger 类吗？ 因为如果没有，我强烈推荐这里。 它将处理您所描述的大数字。 如果这还不够好，那么您需要通过执行 -Xmx 作为命令行参数来分配更多内存供 JVM 使用。 这里有一个例子：

http ://www.coderanch.com/t/384456/Java-General-intermediate/java/Increase-JVM-heap-size-eclipse

如果您需要十进制数大，还有一个 BigDecimal出色地。

Answer 5

由于 Java 堆大小的限制，我也遇到过类似的问题。 没有使用高内存整数，而是转换为布尔值解决了这个问题。
找到附件中的代码：

public ArrayList<Integer> sieve(int A) {
    boolean prime [] = new boolean[A + 1];
    Arrays.fill(prime, true);
    prime[0] = prime[1] = false;

    for (int i = 2; i <= A; i++) {
        if (!prime[i])
            continue;

        for (long j = 1L * i * i; j <= (long) A; j += i)
            prime[(int) j] = false;
    }

    ArrayList<Integer> res = new ArrayList<>();

    for (int i = 0; i <= A; i++) {
        if (prime[i])
            res.add(i);
    }

    return res;
}