用python求出2000000内所有素数的和?不知怎么写? 用Python编出200W以内的质数的和,要求运算时间在10...
import itertools
import time
N = 2000000
L = range(N)
def findnxt(s):
flag = 0
for n in itertools.ifilter(None, L[s+1:]):
return n
t0 = time.time()
n = 2
X = int(N ** .5)
while n < X:
for i, x in enumerate(L[::n][1:]):
if i==0: continue
L[x] = 0
n = findnxt(n)
t1 = time.time()
print "Process usage", t1-t0
l = filter(None, L)
print len(l)
#~ >python -u "baidu.py"
#~ Process usage 13.3068089485
#~ 148934
#~ >Exit code: 0 Time: 13.651
今天见到另一个代码,非常棒(sorry, 忘记了出处)
#!/usr/bin/python
# encoding: utf-8
import itertools
import time
N = 2000000
def clear(aPrime,aList,maxNum):
for i in xrange(aPrime, maxNum, aPrime):
aList[i]=0
def allPrime(maxNum):
aList = range(0,maxNum)
prime = []
for i in xrange(2,len(aList)):
if aList[i] != 0:
prime.append(aList[i])
clear(aList[i],aList,maxNum)
return prime
t0 = time.time()
primelist = allPrime(N)
t1 = time.time()
print len(primelist ),
print '[%s .. %s]' %(
','.join(map(str,
primelist [:10])),
','.join(map(str,
primelist [-10:])),
)
print "Process usage", t1-t0
#~ >python -u "baidu.py"
#~ 148933 [2,3,5,7,11,13,17,19,23,29 .. 1999853,1999859,1999867,1999871,1999889,1999891,1999957,1999969,1999979,1999993]
#~ Process usage 1.31931495667
#~ >Exit code: 0 Time: 1.449
def sundaram3(max_n):
numbers=range(3,max_n+1,2)
half=(max_n)//2
initial=4
for step in xrange(3,max_n+1,2):
for i in xrange(initial,half,step):
numbers[i-1]=0
initial+=2*(step+1)
if initial>half:
return[2]+filter(None,numbers)
print(sum(sundaram3(2000000)))
http://baike.baidu.com/link?url=E3vgFp2GdYBHzDx_CaDVOGj8Wd9x7HxLglzz_jqNSCU4jk1OFeQsvA2MDGLmy9Qfa_dgqb9Cd0Ed2YKCMDj1O_
#!/usr/local/bin/python
def isprime(num):
if n == 2:
return 1
i = 2
flag = 1
while i < num / 2 + 1:
if num % i == 0:
flag = 0
i = i + 1
return flag
sum = 0
n = 2
while n <= 2000000:
if isprime(n):
#print "got n = ", n
sum = sum + n
n = n + 1
print "prime sum 0-2000000: ", sum
但是这样控制到cpu10秒,做不到,可能你们学的有什么快速算法。
要想加快速度,用pypy代替cpython执行代码,实在不行多开进程分段计算。
python2000000以内素数和,求思路~
原理:找到一个素数,把他的倍数全划掉(肯定不是素数),所以求2000000以内的素数,从2开始,把他的倍数划掉(设为false),再找下一个没被划掉的数(肯定是素数,因为他没被划掉,所以不是任何小于他的素数的倍数),再把他的倍数划掉,最后对整个数组处理一遍,没被划掉的数就是所有的素数
def main(): nums = range(2, 2000000) length = len(nums) for i in xrange(length): if nums[i] == 0: continue # nums[i] is now a prime p = nums[i] # remove all a * nums[i] for j in xrange(i + p, length, p): nums[j] = 0 return sum(nums)print main()我自己电脑1秒跑完。。。。
用了筛法,不需要什么sqrt()。
pascal求解,并说说各题原理。
答:ans,n,i,k,tmp:longint;begin read(n,k); for i:=1 to n do read(ar[i]); tmp:=0; for i:=1 to k do tmp:=tmp+ar[i];//算出a[1]+a[2]+...+a[k] ans:=tmp; for i:=k+1 to n do//枚举所有的长度为k的段,以i为结尾 begin tmp:=tm...
图计算引擎Neo4j和Graphscope有什么区别?
答:Neo4j是单机系统,主要做图数据库。GraphScope是由阿里巴巴达摩院智能计算实验室研发的图计算平台,是全球首个一站式超大规模分布式图计算平台,并且还入选了中 国科学技术协会“科创中 国”平台。Graphscope的代码在github.com/alibaba/graphscope上开源。SSSP算法上,GraphScope单机模式下平均要比Neo4j快176.38...
求大神翻译一个Python的代码
答:直接print 哇 每执行一句就加个 print 把 size=2000000 调小一点 size=10 for index, is_primer in enumerate(numbers[:end])这个地方 就是取 数组numbers[:end] 从开始 到end 长度里面的元素 的下标(索引),以及值 例如 [1,2,3] 的 1 的下标就是0,值 1 2 的下标就是1,值 2 3 ...