我有一个排序数组 a，大小为 2*105 且 1≤A[i]≤1010 包含素数和合数。生成的数字如下所示:
a[1] = 1
for i > 1
a[i] = a[i-1]+(i/2)
如何有效地从数组中删除合数？一种解决方案是使用 Rabin-Miller 检查每个元素的素性。有没有更有效的解决方案？
最佳答案
请注意，您的递归关系具有以下闭合形式表达式:
a[i] = floor([i/2]^2) + 1
因此，您在此数组中查找的素数类别为 near-square primes和 resources exist当 i 为偶数时提供一些附加信息。如果仅此而已，那可能就足够了。
但是，事实并非如此。当i是奇数时，就有点困难了。我找不到这种情况的解决方案，并且被迫得出结论，找到通用解决方案的最佳方法是足够大的 Sieve of Erasthenes作为检查所有 i 的 a[i] 素数的基础。由于 a[20000] = (1e8)+1，正确实现的筛子将需要大约 1.25e7 字节(约 13MB)的内存。虽然它很大，但在大多数现代计算机上仍然可以管理。当然，如果这是针对嵌入式系统...
关于arrays - 从数组中删除所有合数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21288216/