3

我正在使用 Eratosthenes 筛解决 Sphere 的 Online Judge Prime Generator 。

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

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

我知道该方法Integer.parseInt()在处理非常大的数字时会引发异常，并且在线法官指示正在引发异常，因此我将代码中的每个案例都更改parseInt为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)
4

5 回答 5

6

这是你的问题：

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

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

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

于 2009-07-03T05:56:56.940 回答
1

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

于 2009-07-03T13:18:17.147 回答
1

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

                    isComposite.set(m);

实际上应该是：

                    isComposite.set(k);

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

于 2016-05-01T01:59:11.563 回答
0

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

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

如果您还需要大的十进制数字，那么还有一个 BigDecimal。

于 2009-07-03T05:47:39.920 回答
0

由于 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;
}
于 2017-07-09T16:52:40.390 回答