猫史档案馆

小学里，大家再也熟悉不过的就是素数（质数）了！这一次，让我来教大家用海龟写素数计算。

我们先用普通的算法：

import math
a=int(input())
c=0
print(str(a)+"以内的素数有：")
for i in range(2, a+1):
    # 素数为True
    ss = True
    for j in range(2, i):
        c+=1
        if (i % j == 0):
            ss = False
            break
    if (ss == True):
        print(i)
print("计算机算了"+str(c)+"次")

我们为了测试，我们输入1W，1W时会很卡，计算机打印出来的也很多，我们就把print（i）注释掉。

这一次，计算机算了5775223，约578W次。

i不必被 2 ~ i之间的每一个整数去除，只需被 2 ~ i的平方根 之间的每一个整数去除就可以了

import math
a=int(input())
c=0
print(str(a)+"以内的素数有：")
for i in range(2, a+1):
    # 素数为True
    ss = True
    for j in range(2, int(math.sqrt(i))+1):
        c+=1
        if (i % j == 0):
            ss = False
            break
    if (ss == True):
        pass
        #print(i)
print("计算机算了"+str(c)+"次")

sqrt是math库里的，所以开头要import math一下

我们还是用1W。

117527次，约12W。这一次还好。

我们定义一个list（列表）名字是L

每一次打印i之后L里面增加i

import math
a=int(input())
c=0
l=[]
print(str(a)+"以内的素数有：")
for i in range(2, a+1):
    # 素数为True
    ss = True
    for j in l:
        c+=1
        #print("j:",j)
        if (i % j == 0):
            ss = False
            break
        if j**2>=i:
            #ss=False
            break
    if (ss == True):
        l.append(i)
        #print(i)
print("计算机算了"+str(c)+"次")

还是1W

44981次，约4W

这就是本期的算法，如果有更好的算法，请在下方评论区评论。