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

我在一个编程网站上遇到了以下问题：Peter希望为他的密码系统生成一些素数。 帮助他！ 您的任务是生成两个给定数字之间的所有素数！

输入

输入以单行中的测试用例数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) break; } } public static void getAnswer() { for (int i = 2; i < 32000 && i = left) { num *= 2; } else { num = (num * (left / num)); if (num = left && j <= right; j += i) { answer[j - left] = true; } } } } } 

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

谢谢，罗希特

Answer 1

你得到了

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

这些都是非常小的数字。 要筛选上限为n的范围，需要素数为√n 。 在这里你知道n <= 10^9 ，所以√n < 31623 ，所以你最需要的是31621的质数。有3401.你可以用几微秒的标准筛子生成它们。

然后你可以通过标记你之前已经过去的素数的倍数来简单地筛选从m到n的小范围，当素数超过√n时停止。 通过从筛子中消除一些小质数的倍数可以获得一些加速，但逻辑变得更复杂（你需要专门处理小米的筛子）。

 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, ie 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 < nm; 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 < nm; i += 2) { if (!sieve[i]) { sievedPrimes[pi++] = m+i; } } return sievedPrimes; } 

使用BitSet或任何其他类型的压缩标志arrays将减少内存使用量，因此可以通过更好的缓存局部性提供显着的加速。

Answer 2

使用BitSet而不是布尔数组。

 public static BitSet primes (final int MAX) { BitSet primes = new BitSet (MAX); // make only odd numbers candidates... for (int i = 3; i < MAX; i+=2) { primes.set(i); } // ... except no. 2 primes.set (2, true); for (int i = 3; i < MAX; i+=2) { /* If a number z is already eliminated (like 9), because it is itself a multiple of a prime (example: 3), then all multiples of z (9) are already eliminated. */ if (primes.get (i)) { int j = 3 * i; while (j < MAX) { if (primes.get (j)) primes.set (j, false); j += (2 * i); } } } return primes; } 

Answer 3

你必须将结果存储在数组中吗？ 如果一个方法计算一个给定的整数是否为素数，如何为{left,left+1,...,right}每个数字调用它？

Answer 4

访问isNotPrime数组时，始终可以使用偏移量。

给定m，n：

 boolean[] isNotPrime = new boolean[n-m+1]; // to now if number x is primer or not boolean xIsPrime = isNotPrime[xm]; 

这里m是偏移量。

Answer 5

您不必强制拥有一个大型数组：您可以保留到目前为止找到的素数列表，并使用多个数组进行测试，其值为= array_slot + offset（已测试的值）。 完成从i到j的值后，将ji添加到offset并从J开始一个新的数组。

您可以从数组中删除偶数，这样可以节省一些空间（values = array_slot * 2 – 1）。

Answer 6

由于m和n之间的距离相对较小，因此您可以在m和n之间的每个数字中强制使用快速素性测试算法。

如果允许概率算法，则可以使用Miller-Rabin测试 。 设M = nm <= 10 ^ 5且N = n <= 10 ^ 9。 蛮力算法的复杂性将是O（k M（log N）^ 3），其中k是控制概率保证的常数（对于实际应用，k可以设置为10）。

对于问题的限制，这种复杂性将在10 ^ 9左右。