V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
black11black
V2EX  ›  问与答

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

  •  
  •   black11black · 2021-01-13 02:46:59 +08:00 via Android · 2168 次点击
    这是一个创建于 1392 天前的主题,其中的信息可能已经有所发展或是发生改变。
    如题,质数算法基本是程序员必修课了,这里就不赘述了,起因是一般测试系统的时候,如果要造成 cpu 密集,我个人是习惯写个质数算法来模拟

    今天写的时候想,这个东西因为优化时间复杂度的算法,后面的搜索要依赖前面的结果,是不是无法多线程并行啊。所以人类的智慧只能单线程算质数?
    16 条回复    2021-01-13 09:53:19 +08:00
    also24
        1
    also24  
       2021-01-13 03:01:06 +08:00
    如果是算质数列表的话,应该是可以通过对筛法做一定改造来优化多线程下的表现的。
    also24
        2
    also24  
       2021-01-13 03:11:13 +08:00
    另,多亏了楼主提到这个素数的事儿,我才突然意识到,经常用到的 Prime95 其实和 GIMPS 有着密切的关联。
    black11black
        3
    black11black  
    OP
       2021-01-13 03:29:43 +08:00
    @also24 啥意思,搜索了一下 GIMPS,所以是一个跑分时兼顾云计算素数的软件?
    yzbythesea
        4
    yzbythesea  
       2021-01-13 03:35:14 +08:00
    如果是多线程,可以直接检查这个数是不是质数来求得所有质数。

    https://gist.github.com/ydzhou/07b22fc641046ff59585b326a582104e
    BrettD
        5
    BrettD  
       2021-01-13 03:54:23 +08:00 via iPhone
    你说的质数算法是什么,是检验一个整数是否是质数,还是什么
    dream4ever
        6
    dream4ever  
       2021-01-13 04:32:51 +08:00
    跑个题,刚知道 V2EX 可以显示 gist 代码,很棒啊
    black11black
        7
    black11black  
    OP
       2021-01-13 04:55:43 +08:00
    @BrettD 寻找 N 以内质数,比如在 10 秒内寻找一百亿以内所有质数,质数一般都说的这个吧。判断单个质数没见过这么出算法题的
    black11black
        8
    black11black  
    OP
       2021-01-13 04:57:12 +08:00
    @yzbythesea 这个就是我用的 cpu bound 的很基础的算法,但是实际上这个算法可能比带缓存的版本慢一百倍,让我想到了并行问题
    yzbythesea
        9
    yzbythesea  
       2021-01-13 05:02:49 +08:00
    @black11black 带缓存是什么意思?
    BrettD
        10
    BrettD  
       2021-01-13 05:09:12 +08:00
    @black11black 实际工程里面判断一个大整数是不是质数的问题比寻找某个范围内所有质数要常见的多吧……所以我看你说的算质数的第一反应是判断质数。寻找范围内质数感觉像是面试时候问的问题。
    BrettD
        11
    BrettD  
       2021-01-13 05:10:42 +08:00
    你的算法“后面依赖前面”是埃拉托色尼筛吗?
    zu1k
        12
    zu1k  
       2021-01-13 06:58:56 +08:00 via Android
    如果缓存中最大的数是 n,那 n 到 2n 这 n 个数实际上不需要依赖额外补充的缓存内容了,也就是说这部分可以利用已有缓存并行计算,不知道我理解的对不对
    thedrwu
        13
    thedrwu  
       2021-01-13 07:51:22 +08:00 via Android
    N 小的时候可以撸个 miller rabin 并行判断
    @black11black #7
    baiyi
        14
    baiyi  
       2021-01-13 07:55:16 +08:00
    楼主说的让我想起了学习 Go 并发时看到的一篇文章,里面用的 Sieve of Eratosthenes 实现素数筛。

    文章里用图形展示了 goroutine 的并发性: https://divan.dev/posts/go_concurrency_visualize/#concurrent-prime-sieve
    black11black
        15
    black11black  
    OP
       2021-01-13 08:43:07 +08:00
    @BrettD 这很基础的问题吧,我觉得不需要解释,而且细节完全是无所谓的问题,不知道你为什么要问这个。算法里实现缓存的办法有很多,比如缓存已判明的质数,比如维护一张全量表等等
    BrettD
        16
    BrettD  
       2021-01-13 09:53:19 +08:00 via iPhone
    @black11black 你不说清楚你的算法是什么,别人怎么并行化。要我并行化的话,我就写成四楼那样了,质数判定用快速近似算法
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3127 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 13:53 · PVG 21:53 · LAX 05:53 · JFK 08:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.