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

• 資深大佬 : also24

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

• 資深大佬 : also24

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

• 主 資深大佬 : black11black

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

• 資深大佬 : yzbythesea

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

  https://gist.github.com/ydzhou/07b22fc641046ff59585b326a582104e  显示 Gist 代码 

• 資深大佬 : 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 你不说清楚你的算法是什么，别人怎么并行化。要我并行化的话，我就写成四那样了，质数判定用快速近似算法