埃拉托斯特尼筛法:加速'交叉倍数”步骤
php小编苹果为您介绍埃拉托斯特尼筛法,这是一种用于快速计算素数的算法。该算法通过不断排除非素数的倍数,从而筛选出所有的素数。与传统的逐个判断素数方法相比,埃拉托斯特尼筛法能够大大加速计算过程。它的核心思想是从2开始遍历到n,将每个素数p的倍数标记为非素数,直到遍历完毕。这种方法在计算大量素数时表现出色,是一种高效的素数计算算法。
问题内容
我已经实现了一个使用埃拉托斯特尼筛法算法列出素数的函数,如下所示:
func ListPrimes(n int) []int { primeList := make([]int, 0) primeBooleans := SieveOfEratosthenes(n) for p := 0; p < n+1; p++ { if primeBooleans[p] == true { primeList = append(primeList, p) } } return primeList } func SieveOfEratosthenes(n int) []bool { primeBooleans := make([]bool, n+1) sqrtN := math.Sqrt(float64(n)) for k := 2; k <= n; k++ { primeBooleans[k] = true } for p := 2; float64(p) <= sqrtN; p++ { if primeBooleans[p] == true { primeBooleans = CrossOffMultiples(primeBooleans, p) } } return primeBooleans } func CrossOffMultiples(primeBooleans []bool, p int) []bool { n := len(primeBooleans) - 1 for k := 2 * p; k <= n; k += p { primeBooleans[k] = false } return primeBooleans }
但我发现效率低下:即 CrossOffMultiples
被调用的次数超出了必要的次数。 IOW,已经被“划掉”的整数将被划掉第二次或第三次(甚至更多次),因为任何多个 m
将有多个因素来划分它。但我似乎无法弄清楚如何利用这一点信息以允许我减少调用 CrossOffMultiples
的次数。我确信有办法做到这一点,但由于某种原因,我无法做到这一点。
有什么建议吗?
解决方法
如果您减少 CrossOffMultiples
被调用的次数,即,您不对某些素数 p
调用它,则 p * p
不会被划掉。但你可以做的是从 p * p
而不是 2 * p
开始循环。
多次划掉数字是正常的,埃拉托斯特尼筛法就是这样做的。 线性筛法是您可能感兴趣的类似算法。 p>
以上是埃拉托斯特尼筛法:加速'交叉倍数”步骤的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

热门话题

OpenSSL,作为广泛应用于安全通信的开源库,提供了加密算法、密钥和证书管理等功能。然而,其历史版本中存在一些已知安全漏洞,其中一些危害极大。本文将重点介绍Debian系统中OpenSSL的常见漏洞及应对措施。DebianOpenSSL已知漏洞:OpenSSL曾出现过多个严重漏洞,例如:心脏出血漏洞(CVE-2014-0160):该漏洞影响OpenSSL1.0.1至1.0.1f以及1.0.2至1.0.2beta版本。攻击者可利用此漏洞未经授权读取服务器上的敏感信息,包括加密密钥等。

Go爬虫Colly中的Queue线程问题探讨在使用Go语言的Colly爬虫库时,开发者常常会遇到关于线程和请求队列的问题。�...

Go语言中用于浮点数运算的库介绍在Go语言(也称为Golang)中,进行浮点数的加减乘除运算时,如何确保精度是�...

本文讨论了GO编程中的GO FMT命令,该命令将代码格式化以遵守官方样式准则。它突出了GO FMT在维持代码一致性,可读性和降低样式辩论方面的重要性。 FO的最佳实践

本文介绍在Debian系统下监控PostgreSQL数据库的多种方法和工具,助您全面掌握数据库性能监控。一、利用PostgreSQL内置监控视图PostgreSQL自身提供多个视图用于监控数据库活动:pg_stat_activity:实时展现数据库活动,包括连接、查询和事务等信息。pg_stat_replication:监控复制状态,尤其适用于流复制集群。pg_stat_database:提供数据库统计信息,例如数据库大小、事务提交/回滚次数等关键指标。二、借助日志分析工具pgBadg

后端学习路径:从前端转型到后端的探索之旅作为一名从前端开发转型的后端初学者,你已经有了nodejs的基础,...
