计划找到所有素数的整数的一个非常大的给定范围 [英] Program to find all primes in a very large given range of integers

问题描述

我碰到一个编程网站这个以下问题： 彼得要产生一些质数他的密码。帮助他！你的任务是产生两个给定数字之间的所有质数！

i came across this following question on a programming website : Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

输入

输入开头的测试用例一行数T（T＆LT; = 10）。在每个接下来的牛逼行有两个数m和n（1＆LT; = M＆LT; = N＆LT; = 10亿，N-M＆LT; = 100000）。用空格隔开

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

我想出了以下解决方案：

I came up with the following solution :

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。

I have edited my solution after reading some of the suggestions. I am still getting a time limit exceeded kind of error. Any more suggestions as how to further optimize this ? Am calculating all the primes upto 32000 and then using these to find the primes between n to m.

谢谢， 罗希特

推荐答案

您给出

1 LT = M＆LT; = N＆LT; = 10亿，N-M＆LT; = 100000

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

这些都是非常小的数字。筛一个范围上限正，你需要的素数为√N。在这里，你知道 N'LT = 10 ^ 9 ，所以√N＆LT; 31623 ，所以你需要在最坏情况下的素数为31621.有3401您可以在几微秒的标准筛生成它们。

these are very small numbers. To sieve a range with an upper bound of n, you need the primes to √n. Here you know n <= 10^9, so √n < 31623, so you need at worst the primes to 31621. There are 3401. You can generate them with a standard sieve in a few microseconds.

然后，你可以简单地筛小范围 M 到 N 通过标记质数你的倍数已经过筛前，当黄金超过√N停止。有些加速可以通过消除从筛孔一些小的素数的倍数来获得，但逻辑变得更加复杂（你需要把筛小 M 特殊）。

Then you can simply sieve the small range from m to n by marking the multiples of the primes you've sieved before, stopping when the prime exceeds √n. Some speedup can be gained by eliminating the multiples of some small primes from the sieve, but the logic becomes more complicated (you need to treat sieves with small m specially).

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

使用位集合或任何其它类型的填充标志阵列的将减少的内存使用，因此可能由于更好的高速缓存局部性得到显著加速。

Using a BitSet or any other type of packed flag-array would reduce the memory usage and thus may give a significant speed-up due to better cache-locality.

这篇关于计划找到所有素数的整数的一个非常大的给定范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！