第一次使用python，所以我在这里使用的一些方法可能看起来有点麻烦。我只是直接将我的c++代码转换为python，这就是我所拥有的(尽管在python中有点慢)
#!/usr/bin/env python
import time
def GetPrimes(n):
Sieve = [1 for x in xrange(n)]
Done = False
w = 3
while not Done:
for q in xrange (3, n, 2):
Prod = w*q
if Prod < n:
Sieve[Prod] = 0
else:
break
if w > (n/2):
Done = True
w += 2
return Sieve
start = time.clock()
d = 10000000
Primes = GetPrimes(d)
count = 1 #This is for 2
for x in xrange (3, d, 2):
if Primes[x]:
count+=1
elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"
pythonw Primes.py
在12.799119秒内找到664579个质数!
#!/usr/bin/env python
import time
def GetPrimes2(n):
Sieve = [1 for x in xrange(n)]
for q in xrange (3, n, 2):
k = q
for y in xrange(k*3, n, k*2):
Sieve[y] = 0
return Sieve
start = time.clock()
d = 10000000
Primes = GetPrimes2(d)
count = 1 #This is for 2
for x in xrange (3, d, 2):
if Primes[x]:
count+=1
elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"
pythonw Primes2.py
在10.230172秒内找到664579个质数!
#!/usr/bin/env python
import time
def GetPrimes3(n):
Sieve = [1 for x in xrange(n)]
for q in xrange (3, n, 2):
k = q
for y in xrange(k*k, n, k << 1):
Sieve[y] = 0
return Sieve
start = time.clock()
d = 10000000
Primes = GetPrimes3(d)
count = 1 #This is for 2
for x in xrange (3, d, 2):
if Primes[x]:
count+=1
elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"
python Primes2.py
在7.113776秒内找到664579个质数!
