埃拉托斯特尼筛法:加速“交叉倍数”步骤

2024年 2月 9日 48.6k 0

埃拉托斯特尼筛法:加速“交叉倍数”步骤

php小编苹果为您介绍埃拉托斯特尼筛法,这是一种用于快速计算素数的算法。该算法通过不断排除非素数的倍数,从而筛选出所有的素数。与传统的逐个判断素数方法相比,埃拉托斯特尼筛法能够大大加速计算过程。它的核心思想是从2开始遍历到n,将每个素数p的倍数标记为非素数,直到遍历完毕。这种方法在计算大量素数时表现出色,是一种高效的素数计算算法。

问题内容

我已经实现了一个使用埃拉托斯特尼筛法算法列出素数的函数,如下所示:

func ListPrimes(n int) []int {
primeList := make([]int, 0)
primeBooleans := SieveOfEratosthenes(n)
for p := 0; p 登录后复制

但我发现效率低下:即 CrossOffMultiples 被调用的次数超出了必要的次数。 IOW,已经被“划掉”的整数将被划掉第二次或第三次(甚至更多次),因为任何多个 m 将有多个因素来划分它。但我似乎无法弄清楚如何利用这一点信息以允许我减少调用 CrossOffMultiples 的次数。我确信有办法做到这一点,但由于某种原因,我无法做到这一点。

有什么建议吗?

解决方法

如果您减少 CrossOffMultiples 被调用的次数,即,您不对某些素数 p 调用它,则 p * p 不会被划掉。但你可以做的是从 p * p 而不是 2 * p 开始循环。

多次划掉数字是正常的,埃拉托斯特尼筛法就是这样做的。 线性筛法是您可能感兴趣的类似算法。 p>

以上就是埃拉托斯特尼筛法:加速“交叉倍数”步骤的详细内容,更多请关注每日运维网(www.mryunwei.com)其它相关文章!

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论