说个闲话，算质数的算法，是不是无法多线程并行？

[black11black]

如题，质数算法基本是程序员必修课了，这里就不赘述了，起因是一般测试系统的时候，如果要造成 cpu 密集，我个人是习惯写个质数算法来模拟

今天写的时候想，这个东西因为优化时间复杂度的算法，后面的搜索要依赖前面的结果，是不是无法多线程并行啊。所以人类的智慧只能单线程算质数？

[also24]

如果是算质数列表的话，应该是可以通过对筛法做一定改造来优化多线程下的表现的。

[also24]

另，多亏了楼主提到这个素数的事儿，我才突然意识到，经常用到的 Prime95 其实和 GIMPS 有着密切的关联。

[black11black]

@also24 啥意思，搜索了一下 GIMPS，所以是一个跑分时兼顾云计算素数的软件？

[yzbythesea]

如果是多线程，可以直接检查这个数是不是质数来求得所有质数。

https://gist.github.com/ydzhou/07b22fc641046ff59585b326a582104e

[BrettD]

你说的质数算法是什么，是检验一个整数是否是质数，还是什么

[dream4ever]

跑个题，刚知道 V2EX 可以显示 gist 代码，很棒啊

[black11black]

@BrettD 寻找 N 以内质数，比如在 10 秒内寻找一百亿以内所有质数，质数一般都说的这个吧。判断单个质数没见过这么出算法题的

[black11black]

@yzbythesea 这个就是我用的 cpu bound 的很基础的算法，但是实际上这个算法可能比带缓存的版本慢一百倍，让我想到了并行问题

[yzbythesea]

@black11black 带缓存是什么意思？

[BrettD]

@black11black 实际工程里面判断一个大整数是不是质数的问题比寻找某个范围内所有质数要常见的多吧……所以我看你说的算质数的第一反应是判断质数。寻找范围内质数感觉像是面试时候问的问题。

[BrettD]

你的算法“后面依赖前面”是埃拉托色尼筛吗？

[zu1k]

如果缓存中最大的数是 n，那 n 到 2n 这 n 个数实际上不需要依赖额外补充的缓存内容了，也就是说这部分可以利用已有缓存并行计算，不知道我理解的对不对

[thedrwu]

N 小的时候可以撸个 miller rabin 并行判断
@black11black #7

[baiyi]

楼主说的让我想起了学习 Go 并发时看到的一篇文章，里面用的 Sieve of Eratosthenes 实现素数筛。

文章里用图形展示了 goroutine 的并发性： https://divan.dev/posts/go_concurrency_visualize/#concurrent-prime-sieve

[black11black]

@BrettD 这很基础的问题吧，我觉得不需要解释，而且细节完全是无所谓的问题，不知道你为什么要问这个。算法里实现缓存的办法有很多，比如缓存已判明的质数，比如维护一张全量表等等

[BrettD]

@black11black 你不说清楚你的算法是什么，别人怎么并行化。要我并行化的话，我就写成四楼那样了，质数判定用快速近似算法