如何高效寻找素数 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何高效寻找素数

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

米青女少 ！

[Jebearssica]

只更新每个合数最小的素数可以优化到O(n)

[Maschinist-LZY]

比如 n = 25，i = 4 时算法会标记 4 × 2 = 8，4 × 3 = 12 等等数字，但是这两个数字已经被 i = 2 和 i = 3 的 2 × 4 和 3 × 4 标记了。
@labuladong 东哥，这里i=4, 4 = 2 x 2, 所以在i=2时4已经被标记为false，所以不会进入内层循环标记吧

[labuladong]

@Maschinist-LZY 嗯，你说得对，我大意了。把 i = 4 改成 i = 5 就没问题了，已修正~

[lihuagang03]

打卡，感谢楼主！

[nuo1nuo]

“首先，回想刚才判断一个数是否是素数的 isPrime 函数，由于因子的对称性，其中的 for 循环只需要遍历 [2,sqrt(n)] 就够了。这里也是类似的，我们外层的 for 循环也只需要遍历到 sqrt(n)”，没明白是怎么类似的？我个人觉得这里能优化成sqrt(n)的原因是内层循环的j被优化成从i^2开始，所以外层循环才可以被优化成sqrt(n)，而不是因为因子对称性

[SUN7700]

也是一样的 你sqrt(n)后面的数 如果不是素数 则已经被标记为了false, 如果是素数则默认就是true, 所以外层循环不用遍历到n 只用遍历到sqrt(n)

[ninja119347]

Chat GPT的回复：在埃拉托斯特尼筛法中，我们只需要筛选到sqrt(n)即可确定小于n的质数。因为如果存在一个大于sqrt(n)的非质数m，那么它一定可以分解成两个小于或等于sqrt(n)的因子，其中之一必然小于或等于sqrt(n)。如果我们遍历到sqrt(n)之后还存在非质数，那么这些非质数的倍数已经被之前的遍历过程标记为非质数了

[yonggui-yan]

打卡。妙哉妙哉，排除法！

[bruceeewong]

20230107 打卡，leetcode看到一个老哥对这种解法提了优化，时间复杂度beats 99%

主要优化点是内外层的for loop都只遍历奇数，确实速度快了一倍。。。

https://leetcode.com/problems/count-primes/solutions/57588/my-simple-java-solution/comments/210313

[scutljh]

给力，筛法确实猛

[PanandSu]

可以借助Go的goroutine，进一步优化筛法

package main

import "fmt"

func generator(ch chan<- int) {
	for i := 2; ; i++ {
		ch <- i
	}
}
func filter(input <-chan int, output chan<- int, prime int) {
	for {
		i := <-input
		if i%prime != 0 {
			output <- i
		}
	}
}
func main() {
	ch := make(chan int)
	//chan可以传参给chan<-,<-chan类型
	go generator(ch)
	//生成25个质数
	for i := 0; i < 25; i++ {
		prime := <-ch
		fmt.Println(prime)
		out := make(chan int)
		go filter(ch, out, prime)
		ch = out
	}
	//ch,out一直是动态变化的,像流水线,一直运行,直到main函数执行完毕,主routine关闭,所有goroutine才关闭
	//如果一个依赖另一个的数据,则必须等待其运行出结果
	//ch,out,1+25=26个goroutine是先后启动,然后一起运行,26个协程并发
	//很像CPU的流水线执行,共同推进程序运行
}