java - SPOJ 上的 PrimeNumber 生成器运行时错误

Question

我试图解决 PrimeNumber Generator SPOJ 上的问题。该代码在 SPOJ 上总是给出运行时错误，但在 ideone.com 上它工作正常。不知道是什么导致了这个问题。我尝试了 Scanner 和 BufferedReader 来读取输入。

import java.lang.*;
import java.io.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(r.readLine());
        while (t > 0) {
            String input = r.readLine();
            int N1 = Integer.parseInt(input.split(" ")[0]);
            int N2 = Integer.parseInt(input.split(" ")[1]);
            boolean isPrime[] = new boolean[N2 + 1];
            int count = 0;
            int primes[] = new int[N2 + 1];
            for (int i = 2; i <= N2; i++) {
                isPrime[i] = true;
            }
            for (int i = 2; i * i <= N2; i++) {
                if (isPrime[i]) {
                    for (int j = 2; i * j <= N2; j++) {
                        isPrime[i * j] = false;
                    }
                }
            }
            for (int i = 2; i <= N2; i++) {
                if (isPrime[i]) {
                    primes[count++] = i;
                }
            }
            for (int i = 2; i <= N2; i++) {
                isPrime[i] = true;
            }
            for (int i = 0; i < count; i++) {
                int p = primes[i];
                int s = N1 / p;
                s = s * p;
                for (int j = s; j <= N2; j = j + p) {
                    if (j < N1) {
                        continue;
                    }
                    isPrime[j - N1] = false;
                }
            }

            for (int i = 0; i < count; i++) {
                if (primes[i] >= N1 && primes[i] <= N2) {
                    System.out.println(" " + primes[i]);
                }
            }
            for (int i = 0; i < (N2 - N1 + 1); i++) {
                if (isPrime[i] == true && (i + N1) != 1) {
                    System.out.println(i + N1);
                }
            }
            System.out.println("");
            t--;
        }
    }
}

我给出的示例输入是

2
10 30
50 100

我发现错误出现在 boolean isPrime[] = new boolean[N2 + 1] 行。 N2 不能取最大 1000000000 的值。

有人可以帮我解决这个问题吗？

Answer 1

您正在使用 boolean 数组:int primes[] = new int[N2 + 1]; 进行埃拉托斯特尼筛法。为了节省空间，请使用位而不是 boolean 值，例如 bitSet。为了节省更多空间，只记录奇数的答案，所有偶数(除2之外)都是合数，因此只要对2进行特殊安排就可以忽略它们；也许是这样的:

if (num % 2 == 0) { return num == 2; }

靠近 isPrime() 方法的开头。这将使所需的存储空间减半。