埃拉托氏菌的筛子问题：处理非常大的数字

Question

我正在解决Sphere的在线法官 Prime Generator 使用Eratosthenes的筛子。

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

输入始于单行中的测试用例数（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)

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上没有错误，吐出4,832个素数从999900017开始，以99999999937结束。该底部使用了125 mbytes，并且该方法在我的2.2 GHz上运行17秒笔记本电脑。

Answer 4

Ae you using the BigInteger class? Because if no, I highly recommend it here. It will deal with the big numbers you are describing. If that is not good enough, then you need to allocate more memory for the JVM to use by doing -Xmx as a command line parameter. There's an example here:

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

There is a BigDecimal as well, if you need decimal numbers to be large as well.

Answer 5

I had faced similar issues due the limitations on Java Heap Size. Instead of using high memory Integer, shifting to boolean solved the problem. Find the attached code:

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