java - 程序在给定的很大整数范围内查找所有素数

我在编程网站上遇到了以下问题:
彼得想为其密码系统生成一些质数。救救他!您的任务是生成两个给定数字之间的所有质数!

输入

输入以一行中的测试用例数t(t
我想出了以下解决方案:

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之间的素数。

谢谢，
罗希特

最佳答案

给你



这些是非常小的数字。要筛选上限为n的范围，需要将素数加到√n。在这里，您知道了n <= 10^9，所以知道了√n < 31623，因此最坏的时候需要质数到31621。有3401。您可以在几微秒内用标准筛子生成它们。

然后，您可以通过标记以前筛选过的质数的倍数来简单筛选m到n的小范围，当质数超过√n时停止。通过从筛子中消除一些小质数的倍数可以提高速度，但是逻辑变得更加复杂(您需要使用小m专门处理筛子)。

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

使用BitSet或任何其他类型的打包标志数组将减少内存使用，因此由于具有更好的缓存局部性，因此可以显着提高速度。

关于java - 程序在给定的很大整数范围内查找所有素数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10703699/