质数

作者: 秋幻旎苏 | 来源:发表于2018-08-09 20:03 被阅读0次

方法一

#%%timeit
#打印10万以内的素数
n = 100000
#除了2 以外的素数,都是奇数
count=1
#print(2,end=' ')
for i in range(3,n,2):
    flag = False
    if i > 10 and  i % 5 == 0 :
        continue
    for j in range(3,int(i**0.5)+1,2):
        if i % j == 0:
            break 
    else:
        print(i,end=' ')
        count += 1
print()
print(count)

方法二

#%%timeit
n = 100000
count = 0
primenumber = []
flag = False

for x in range(2,n):
    edge = int(x**0.5)
    for i in primenumber:
        if x % i == 0:
            flag = True
            break
     #  if i > x ** 0.5.如果每次进入循环重新计算,就会消耗性能
        if i > edge:
            flag = False
            break
    if not flag :
        primenumber.append(x)
        count += 1
        
print(count)

方法三

#%%timeit
count = 2
#print(2, end=' ')
#print(3, end=' ')
number = 100000
for num in range(5,number,2):
  #大于6的质数除以6,余数都是1或者5
    if num % 6 != 1 and num % 6 != 5:
        continue
    else :
        flag = False
        if num < 30 :
            for i in range(3,num,2):
                if not ( num % i ):
                    flag = False
                    break
                else:
                    flag = True
        else:
            for i in range(5,int(num**0.5 + 1),6):
                if ( not num % i ) or ( not num % (i+2) ):
                    flag = False
                    break
                else:
                     flag = True
    if flag :
        print(num, end= ' ')
        count += 1
print()
print(count)

方法四

#%%timeit
count = 2 
lst = [2,3]
n = 100000
x = 5 # 6的倍数前后都是奇数
step = 2 
#大于3的素数只有6N-1和6N+1两种形式,如果6N-1和6N+1都是素数成为孪生素数
while x <= n:  #被除数从5开始,7,11,13....
    for i in range(3,int(x**0.5)+1,2):  # 除数是素数列表
        if x % i == 0 :
            break
    else:
        count += 1
        lst.append(x)
    x += step 
    step = 4 if step == 2 else 2
    
print(count)

方法五 效率最快

#%%timeit
count = 2 
lst = [2,3]
n = 100000
x = 5
step = 2 
while x <= n:  #被除数从5开始,7,11,13....
    edge = int(x**0.5)
    for i in lst:  # 除数是素数列表
        if x % i == 0 :
            break
        if i > edge:
            break
    else:
        count += 1
        lst.append(x)
    x += step 
    step = 4 if step == 2 else 2
print(count)

相关文章

网友评论

      本文标题:质数

      本文链接:https://www.haomeiwen.com/subject/ejncbftx.html