python 质数 埃拉托色尼筛法 [英] python prime numbers Sieve of Eratosthenes
问题描述
谁能告诉我如何在这段代码中实现 Eratosthenes 的筛分以使其更快?如果您能用筛子完成它,我们将不胜感激.在这个特定的代码中,我真的很难做到这一点.
#!/usr/bin/env python导入系统T=10 #测试用例数t=open(sys.argv[1],'r').readlines()导入数学def is_prime(n):如果 n == 2:返回真如果 n%2 == 0 或 n <= 1:返回错误sqr = int(math.sqrt(n)) + 1对于范围(3,sqr,2)中的除数:如果 n%divisor == 0:返回错误返回真#每个测试用例的第一行a=[1,4,7,10,13,16,19,22,25,28]计数=0因为我在一个:b=t[i].split(" ")c=b[1].split("\n")[0]b=b[0]对于 xrange(int(b)) 中的 k:d=t[i+1].split(" ")e=t[i+2].split(" ")对于 d 中的 g:对于 e 中的 j:尝试:总和=整数(g)+整数(j)p=is_prime(sum)如果 p==真:计数+=1打印计数别的:经过除了:尝试:g=g.strip("\n")总和=整数(g)+整数(j)p=is_prime(sum)如果 p==真:计数+=1打印计数别的:经过除了:j=j.strip("\n")总和=整数(g)+整数(j)p=is_prime(sum)如果 p==真:计数+=1打印计数别的:经过打印最终计数"+计数
在 Python 中加速筛选的一个老技巧是使用花哨的 ;-) 列表切片表示法,如下所示.这使用 Python 3.Python 2 所需的更改在注释中注明:
定义筛(n):返回所有质数 <= n."np1 = n + 1s = list(range(np1)) # 在 Python 2 中去掉 `list()`s[1] = 0sqrtn = int(round(n**0.5))for i in range(2, sqrtn + 1): # 在 Python 2 中使用 `xrange()`如果 s[i]:# 下一行:在 Python 2 中使用 `xrange()`s[i*i: np1: i] = [0] * len(range(i*i, np1, i))返回过滤器(无,s)
在 Python 2 中,它返回一个列表;在 Python 3 中是一个迭代器.在 Python 3 下:
<预><代码>>>>清单(筛(20))[2, 3, 5, 7, 11, 13, 17, 19]>>>len(list(sieve(1000000)))78498那些人都眨了眨眼.鉴于此,以下是构建 is_prime
函数的方法:
primes = set(sieve(the_max_integer_you_care_about))def is_prime(n):在素数中返回 n
是 set()
部分使它变得更快.当然,这个函数很简单,你可能想写:
如果 n 是素数:
直接而不是搞乱:
if is_prime(n):
Hi can anyone tell me how to implement Sieve of Eratosthenes within this code to make it fast? Help will be really appreciated if you can complete it with sieve. I am really having trouble doing this in this particular code.
#!/usr/bin/env python
import sys
T=10 #no of test cases
t=open(sys.argv[1],'r').readlines()
import math
def is_prime(n):
if n == 2:
return True
if n%2 == 0 or n <= 1:
return False
sqr = int(math.sqrt(n)) + 1
for divisor in range(3, sqr, 2):
if n%divisor == 0:
return False
return True
#first line of each test case
a=[1,4,7,10,13,16,19,22,25,28]
count=0
for i in a:
b=t[i].split(" ")
c=b[1].split("\n")[0]
b=b[0]
for k in xrange(int(b)):
d=t[i+1].split(" ")
e=t[i+2].split(" ")
for g in d:
for j in e:
try:
sum=int(g)+int(j)
p=is_prime(sum)
if p==True:
count+=1
print count
else:
pass
except:
try:
g=g.strip("\n")
sum=int(g)+int(j)
p=is_prime(sum)
if p==True:
count+=1
print count
else:
pass
except:
j=j.strip("\n")
sum=int(g)+int(j)
p=is_prime(sum)
if p==True:
count+=1
print count
else:
pass
print "Final count"+count
An old trick for speeding sieves in Python is to use fancy ;-) list slice notation, like below. This uses Python 3. Changes needed for Python 2 are noted in comments:
def sieve(n):
"Return all primes <= n."
np1 = n + 1
s = list(range(np1)) # leave off `list()` in Python 2
s[1] = 0
sqrtn = int(round(n**0.5))
for i in range(2, sqrtn + 1): # use `xrange()` in Python 2
if s[i]:
# next line: use `xrange()` in Python 2
s[i*i: np1: i] = [0] * len(range(i*i, np1, i))
return filter(None, s)
In Python 2 this returns a list; in Python 3 an iterator. Here under Python 3:
>>> list(sieve(20))
[2, 3, 5, 7, 11, 13, 17, 19]
>>> len(list(sieve(1000000)))
78498
Those both run in an eyeblink. Given that, here's how to build an is_prime
function:
primes = set(sieve(the_max_integer_you_care_about))
def is_prime(n):
return n in primes
It's the set()
part that makes it fast. Of course the function is so simple you'd probably want to write:
if n in primes:
directly instead of messing with:
if is_prime(n):
这篇关于python 质数 埃拉托色尼筛法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!