求n以内的素数
常规取模优化
-
- 只测试 >2 的奇数，因为大于2的质数只可能是奇数
-
- 奇数只和一个奇数取模，因为奇数不能被合数整除
-
- 找到开方点 [3,int(x**0.5)+1]
import datetime
start = datetime.datetime.now()
n=100000
count=1 #2是偶素数
for x in range(3,n,2):
for i in range(3,int(x**0.5)+1,2):
if x%i == 0:
break
#for循环中if条件不满足且不被break,则执行else,可使用flag
else:
count+=1
end = datetime.datetime.now()
delta = (end - start).total_seconds()
print(count,delta)
print(delta)
9592 0.213215
将素数存为列表判断
start = datetime.datetime.now()
n=100000
count=2 #偶数2是质数
primenubmer=[3]
for x in range(5,n,2):
if x % 5 == 0:
continue
edge=int(x**0.5)
flag = False #假设这趟的当前x不是质数
for i in primenubmer: #全质数遍历，要考虑开方点
if i > edge: #质数i大于开方点，说明x是质数，不用往后走了
flag=True #找到质数跳出
break
if x%i == 0:
break #是合数
if flag:
count+=1 #是质数
primenubmer.append(x)
#若使用for else 遇到break不会执行，这里要使用flag
end=datetime.datetime.now()
delta=(end-start).total_seconds()
print(count,delta)
9591 0.145517