9 algorithm optimization primes sieve-of-eratosthenes primality-test
给定n,求m使得m是小于n的最小半素.
下一个素数非常简单,半素质不那么简单.需要说明的是,只需要半刚性,尽管同时获取因子会很方便.
我想到了一些方法,但我确信有更好的方法.
算术运算假定为O(1).我使用了Eratosthenes的Sieve,它是O(n log log n),我知道Atkin的Sieve,但我喜欢我的半优化的Eratosthenes.
从n开始计数,当你找到半数时停止.
这看起来真的很愚蠢但如果有一个O(log n)半素测试或O(1)测试给出下面的素数,这可能比其他2更快.
Semiprime分布似乎远高于主要分布,因此通过良好的半素测试,这实际上可能优于O(n).
定义prev(x)和next(x)并分别给出上一个和下一个素数,如果素数存储在树中或使用列表二进制搜索,则可以是O(log n).
先做筛子.
从p = prev(sqrt(n))开始,q = next(n/p).当pq <= n时,转到下一个q.如果pq小于目前为止的最小值,则将其记录为新的最小值.继续前一个p,直到用完p进行测试.
这可以保证找到正确答案,但速度相当慢.仍然是O(n log n),所以也许可以接受.
像往常一样从筛子开始.为O(1)素性测试创建筛子的哈希集视图.
从p = 2开始.通过素数迭代到sqrt(n).对于每个p,得到q =(((n/p + 1)/ 2)*2)+1 =(((n/p + 1)>> 1)<< 1)| 1.虽然到目前为止pq小于最小值且q不是素数,但是将q加2.如果pq仍小于最小值,则将其记录为新的最小值.
我在Java中实现了#1和#3,两者都使用了相同的Eratosthenes Sieve实现.大部分的运行时间都花在筛选上,所以如果要进行优化,那就是在筛子中.在一些优化之后,向上计数(#1)击败计数(#3),在最后一次和最大测试(11位十进制数n)中快两倍.
但仍然有希望,因为需要延长筛子的距离取决于最大数量的主要测试.如果存在具有较低质数测试界限的半素测试,则计数方法可能更快.
当然有一个更好的算法？或者至少有更好的方法来实现这个？