V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
napretep
V2EX  ›  Python

如何用 python 计算十亿内的素数总和?

  •  
  •   napretep · 2015-04-18 03:15:08 +08:00 · 8383 次点击
    这是一个创建于 3501 天前的主题,其中的信息可能已经有所发展或是发生改变。
    今天想加个QQ群,得回答这个问题才能通过请求。
    我本来想想很简单啊用下面这个式子就能算了。
    reduce(lambda x,y:x+y,[x for x in range(1,N+1,2) if len([y for y in range(1,x+1,2) if x%y==0])==2],2)
    结果到后来抛出个错误说MemoryError。
    研究了好会儿还是没什么好法子,各位有什么看法?
    21 条回复    2015-04-19 00:03:00 +08:00
    ppdg
        1
    ppdg  
       2015-04-18 03:49:42 +08:00 via Android
    最快的应该是筛法吧
    msg7086
        2
    msg7086  
       2015-04-18 07:16:08 +08:00
    筛法用C++大概1分钟内能出结果。你这个式子建议你先算算要多少内存和运算量吧……
    ybbswc
        3
    ybbswc  
       2015-04-18 07:20:25 +08:00
    这个range太大了。所以抛出error吧。
    http://www.zhihu.com/question/29580448
    知乎上有这个提问,不过好多都是C的。
    illuz
        4
    illuz  
       2015-04-18 08:58:00 +08:00   ❤️ 1
    Python 的话,去数学网站上爬呀,比如:
    http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php
    http://www.bigprimes.net/archive/prime/
    第二个会好爬点,不过也要爬个 6w 页的说。
    网上爬总比爆内存好...
    futursolo
        5
    futursolo  
       2015-04-18 09:10:55 +08:00
    使用生成器可以避免上面所说的内存不够用的情况。

    这里给一个例子:(V2EX会把代码中的空格自动删掉,请自己补全)

    import math
    import time


    def is_prime(number):
    if number > 1:
    if number == 2:
    return True
    if number % 2 == 0:
    return False
    for current in range(3, int(math.sqrt(number) + 1), 2):
    if number % current == 0:
    return False
    return True
    return False


    def get_primes(number):
    while True:
    if is_prime(number):
    yield number
    number += 1

    start = time.time()

    prime = get_primes(1)
    prime_sum = 0
    while True:
    this_prime = next(prime)
    if this_prime <= 1000000:#改一下这里的数字
    prime_sum += this_prime
    else:
    break
    print("Result:" + str(prime_sum))
    print ("Finished! Time Used: " + str(time.time() - start) + "s.")

    至于楼上所说的筛法算素数的问题,可能也需要比较大的内存
    (你还是要把已经算出来的素数保存起来,在这里暂时不用了)

    这个是Python3的代码,Python2请自己改一下。

    要想算的快一点,可以使用PyPy3。
    sinux
        6
    sinux  
       2015-04-18 09:45:02 +08:00
    写了一个比较朴素的,内存倒是没爆...

    def print_prime(n):
    ____q = 0
    ____for i in xrange(0, n):
    ________found = True
    ________for j in xrange(2, i):
    ________if i % j == 0:
    ____________found = False
    ____________break
    ________if found:
    ____________q += i
    ____print q


    if __name__ == '__main__':
    ____print_prime(1000000000)
    sinux
        7
    sinux  
       2015-04-18 09:46:04 +08:00
    这缩进不忍直视
    em70
        8
    em70  
       2015-04-18 10:08:45 +08:00 via Android
    除了2以外,素数不可能是偶数,能降低一半的计算量
    sandideas
        9
    sandideas  
       2015-04-18 10:30:42 +08:00 via Android
    用c语言计算,然后用python输出
    broono
        10
    broono  
       2015-04-18 10:34:18 +08:00
    首先两位数以上以0,2,4,5,6,8结尾的数字,然后撒欢吧=-=先排除掉,能不算的就不算,内存就节省出来了。
    wy315700
        11
    wy315700  
       2015-04-18 10:34:30 +08:00
    @sandideas
    @em70
    @sinux

    果然说程序员算法差不是吹的,,,

    http://blog.csdn.net/dinosoft/article/details/5829550

    看看快速线性筛法吧。。。
    bcxx
        12
    bcxx  
       2015-04-18 10:46:19 +08:00
    筛法保平安……
    tigerstudent
        13
    tigerstudent  
       2015-04-18 12:05:55 +08:00
    之前为了提高博客访问量写了一篇博文描述了秒解的算法,一千多点击量。后来觉得实在没意思就删了。
    Kirscheis
        14
    Kirscheis  
       2015-04-18 12:40:14 +08:00 via iPhone
    python用素数筛的话十亿以内只需要7G左右内存而已。
    Septembers
        15
    Septembers  
       2015-04-18 12:45:29 +08:00 via Android
    @futursolo @sinux
    代码可以发gist
    imn1
        16
    imn1  
       2015-04-18 13:48:56 +08:00
    XadillaX
        17
    XadillaX  
       2015-04-18 14:28:12 +08:00
    素数筛法。
    gladuo
        18
    gladuo  
       2015-04-18 15:39:47 +08:00
    @wy315700 朴素筛法也就十来秒钟吧
    个数 素数
    的组合打印也就900M吧
    建议算出来用py加就好。。。
    wy315700
        19
    wy315700  
       2015-04-18 15:43:02 +08:00
    @gladuo 楼上好多N^2的算法。。。
    ant_sz
        20
    ant_sz  
       2015-04-18 16:18:31 +08:00
    如果用 BitSet 来做筛法的话空间会减少很多,可惜 Python 标准库里好像没有 BitSet 的实现。
    monkeymonkey
        21
    monkeymonkey  
       2015-04-19 00:03:00 +08:00 via Android
    只要求和的话,把素数表存成文件扫一遍不就算出和了么,也不需要多少内存。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2718 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 06:34 · PVG 14:34 · LAX 22:34 · JFK 01:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.