1
ppdg 2015-04-18 03:49:42 +08:00 via Android
最快的应该是筛法吧
|
2
msg7086 2015-04-18 07:16:08 +08:00
筛法用C++大概1分钟内能出结果。你这个式子建议你先算算要多少内存和运算量吧……
|
3
ybbswc 2015-04-18 07:20:25 +08:00
|
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 页的说。 网上爬总比爆内存好... |
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。 |
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) |
7
sinux 2015-04-18 09:46:04 +08:00
这缩进不忍直视
|
8
em70 2015-04-18 10:08:45 +08:00 via Android
除了2以外,素数不可能是偶数,能降低一半的计算量
|
9
sandideas 2015-04-18 10:30:42 +08:00 via Android
用c语言计算,然后用python输出
|
10
broono 2015-04-18 10:34:18 +08:00
首先两位数以上以0,2,4,5,6,8结尾的数字,然后撒欢吧=-=先排除掉,能不算的就不算,内存就节省出来了。
|
11
wy315700 2015-04-18 10:34:30 +08:00
@sandideas
@em70 @sinux 果然说程序员算法差不是吹的,,, http://blog.csdn.net/dinosoft/article/details/5829550 看看快速线性筛法吧。。。 |
12
bcxx 2015-04-18 10:46:19 +08:00
筛法保平安……
|
13
tigerstudent 2015-04-18 12:05:55 +08:00
之前为了提高博客访问量写了一篇博文描述了秒解的算法,一千多点击量。后来觉得实在没意思就删了。
|
14
Kirscheis 2015-04-18 12:40:14 +08:00 via iPhone
python用素数筛的话十亿以内只需要7G左右内存而已。
|
15
Septembers 2015-04-18 12:45:29 +08:00 via Android
|
16
imn1 2015-04-18 13:48:56 +08:00
|
17
XadillaX 2015-04-18 14:28:12 +08:00
素数筛法。
|
20
ant_sz 2015-04-18 16:18:31 +08:00
如果用 BitSet 来做筛法的话空间会减少很多,可惜 Python 标准库里好像没有 BitSet 的实现。
|
21
monkeymonkey 2015-04-19 00:03:00 +08:00 via Android
只要求和的话,把素数表存成文件扫一遍不就算出和了么,也不需要多少内存。
|