我需要从2开始按升序查找一定数量的素数.我有一个工作算法,它采用数字限制作为参数 - 它找到所有小于限制的素数.
例如 - 对于param,20它会返回2,3,5,7,11,13,17,19,但我需要输入5并获取2,3,5,7,11.什么是最好的方法？我正在使用Eratosthenes的Sieve,并且没有办法限制数字删除部分,因为我不知道第195个素数有多大,因此我不知道是否应该删除所有2的倍数到1568或1268426.我希望问题很清楚,谢谢你的帮助
有几种方法可以做你想要的.
素数定理表明,小于n的素数的数量渐近等于n/log(n).您可以添加一个小缓冲区,然后执行Eratosthenes筛选,并抛弃超出限制的任何质数.
有些公式可以计算小于n的精确素数而不列出素数.您可以使用其中一个公式来查找第n个素数,然后使用Sieve来制作素数列表.谷歌的"Legendre sum"和"Lehmer的公式"如果你想采取这种方法.
你可以使用分段的Eratosthenes筛子.筛分到一些方便的限制.如果你有答案,请停止.否则,选择下一个段,然后选择下一个段,依此类推,直到找到所需的素数.
有一种非常聪明的方法可以生成无限的素数列表,用优先级队列替换Eratosthenes的Sieve的位数组.谷歌为梅丽莎奥尼尔的论文真正的Eratosthenes筛选.
您可以在此处查看所有这些算法的完整说明和实现.
顺便说一下,第195个素数是1187.有247个素数低于1568,而97790素数少于1268426.
| 归档时间： |
|
| 查看次数： |
5416 次 |
| 最近记录： |