Первый раз, используя 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
Найдено 664579
blockquote>#!/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
Найдено 664579 простых чисел за 10.230172 секунд!
blockquote>#!/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
Найдено 664579 простых чисел в 7.113776 секунд!
blockquote>