编程以查找非常大的给定整数范围内的所有素数

Question

我在一个编程网站上遇到了以下这个问题:彼得希望为他的密码系统生成一些素数.帮助他!你的任务是生成两个给定数字之间的所有素数!

输入

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

我提出了以下解决方案:

import java.util.*;

public class PRIME1 {
    static int numCases;
    static int left, right;
    static boolean[] initSieve = new boolean[32000];
    static boolean[] answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        numCases = sc.nextInt();
        initSieve[0] = true;
        initSieve[1] = true;
        Sieve();
        for (int j = 0; j < numCases; j++) {
            String line = sc.next();
            String line2 = sc.next();
            left = Integer.parseInt(line);
            right = Integer.parseInt(line2);
            answer = new boolean[right - left + 1];
            getAnswer();
            for (int i = 0; i < answer.length; i++) {
                if (!answer[i]) {
                    int ans = i + left;
                    System.out.println(ans);
                }
            }
            System.out.println();
        }
    }

    public static void Sieve() {

        for (int i = 2; i < 32000; i++) {
            if (!initSieve[i]) {
                for (int j = 2 * i; j < 32000; j += i) {
                    initSieve[j] = true;
                }
            }
            if (i * i > 32000)
                break;
        }
    }

    public static void getAnswer() {
        for (int i = 2; i < 32000 && i <= right; i++) {
            if (!initSieve[i]) {
                int num = i;
                if (num * 2 >= left) {
                    num *= 2;
                } else {
                    num = (num * (left / num));
                    if (num < left)
                        num += i;
                }
                for (int j = num; j >= left && j <= right; j += i) {
                    answer[j - left] = true;
                }
            }
        }
    }
}

我在阅读了一些建议后编辑了我的解决方案.我仍然得到超出时间限制的错误.还有更多建议如何进一步优化这个？我计算所有素数高达32000,然后用这些素数找到n到m之间的素数.

谢谢,罗希特

Answer 1

你被给予

\n\n

\n

1 <= m <= n <= 1000000000, nm<=100000

\n

\n\n

这些数字非常小。要筛选上限为 的范围n，您需要 的素数\xe2\x88\x9an。在这里你知道n <= 10^9，所以\xe2\x88\x9an < 31623，所以你最多需要 31621 的素数。有 3401 个。你可以用标准筛在几微秒内生成它们。

\n\n

然后，您可以简单地通过标记您之前筛选过的素数的倍数来筛选从m到 的小范围，当素数超过 时停止。通过从筛子中消除一些小素数的倍数可以获得一定的加速，但逻辑变得更加复杂（需要特殊对待小素数的筛子）。n\xe2\x88\x9anm

\n\n

public int[] chunk(int m, int n) {\n    if (n < 2) return null;\n    if (m < 2) m = 2;\n    if (n < m) throw new IllegalArgumentException("Borked");\n    int root = (int)Math.sqrt((double)n);\n    boolean[] sieve = new boolean[n-m+1];\n    // primes is the global array of primes to 31621 populated earlier\n    // primeCount is the number of primes stored in primes, i.e. 3401\n    // We ignore even numbers, but keep them in the sieve to avoid index arithmetic.\n    // It would be very simple to omit them, though.\n    for(int i = 1, p = primes[1]; i < primeCount; ++i) {\n        if ((p = primes[i]) > root) break;\n        int mult;\n        if (p*p < m) {\n            mult = (m-1)/p+1;\n            if (mult % 2 == 0) ++mult;\n            mult = p*mult;\n        } else {\n            mult = p*p;\n        }\n        for(; mult <= n; mult += 2*p) {\n            sieve[mult-m] = true;\n        }\n    }\n    int count = m == 2 ? 1 : 0;\n    for(int i = 1 - m%2; i < n-m; i += 2) {\n        if (!sieve[i]) ++count;\n    }\n    int sievedPrimes[] = new int[count];\n    int pi = 0;\n    if (m == 2) {\n        sievedPrimes[0] = 2;\n        pi = 1;\n    }\n    for(int i = 1 - m%2; i < n-m; i += 2) {\n        if (!sieve[i]) {\n            sievedPrimes[pi++] = m+i;\n        }\n    }\n    return sievedPrimes;\n}\n

\n\n

使用一个BitSet或任何其他类型的打包标志数组将减少内存使用，并因此可以由于更好的缓存局部性而显着加速。

\n