Python 判断素数

Prime Number

Posted by BlueFat on Monday, August 1, 2022

求n以内的素数

常规取模优化

    1. 只测试 >2 的奇数,因为大于2的质数只可能是奇数
    1. 奇数只和一个奇数取模,因为奇数不能被合数整除
    1. 找到开方点 [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