找质数 【土方法】#小学生 Python 通俗易懂

相信现在各位看官都在小学阶段学习过质数，但那时年纪尚小，听质数这个数学名词很陌生，在老师的讲述后才有所理解

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。又称素数。

质数应用方面十分广泛，特别是计算机方面，如RSA算法等

大家小学时应该找过100以内的质数，当时老师使用一个方法，我现在仍记忆犹新

根据定理，因为质数只有两个因数，所以我们采用找出多余因数的方法排除合数，因而找出质数：

先依次将2到100的数写在纸上，再将尾数0，2，4，5，6，8，的数（2和5的倍数，2和5除外）排除，然后使用乘法口诀将3，7，9是的倍数的数字排除，但是还有点小纰漏，可以这样解决，先将个位和十位相同的数排除（是11的倍数，11除外

），再将各个位数的数字加起来判断是否为3的倍数。这样下来，我们找出了26个数，翻书验证，91不在质数表里面

因为我们没考虑到7乘大于等于10的倍数（前面的方法成功避开7乘10到12的倍数），13乘7等于91。

总而言之，100以内的质数有25个

100以内的质数表

如果按照上面的方法找出200以内的质数，那么Bug会更多，还好当时考试范围只考100以内的质数，之后背质数表到如今还记得（老师教授上文的方法只是为了方便记忆和方便理解质数概念）

学习后我萌生写程序找质数的念头，因为某加密算法应用到质数

我根据当初老师给我的思路写了个程序，虽然现在有些算法更好，但我也硬着头皮上了

我们先输入一个数表示其范围，将其赋值到变量a中

a = int(input())

使用for循环语句创建1到a的序列，即for x in range(1,a+1): 之后依次找出x的因数个数，将其赋值到变量b上，

代码如下

for x in range(1,a+1):
    b = 0
    for y in range (1,x+1):
        if x%y == 0:
            b += 1

最后判断因数个数，如果b的值为2，那么x为质数，随后打印x

完整代码如下

a = int(input())
b = 0
for x in range(1,a+1):
    b = 0
    for y in range (1,x+1):
        if x%y == 0:
            b += 1
    if b == 2:
        print(x)

这种土方法叫枚举法，又叫穷举法，俗称暴力搜索法

应该有小伙伴发现，如果输入数字过大的话，需要花长时间计算，

而且在第5行开始代码觉得有点冗余

我们可以这样修改，如果b大于3就跳出循环

a = int(input())
b = 0
c = 0
for x in range(1, a+1):
    b = 0
    for y in range(1, x+1):
        if b > 3:
            break
        else:
            if x % y == 0:
                b += 1
    if b == 2:
        print(x)
        c +=1
print(c)

修改前后其时间复杂度均为为O（n²）

相对而言，修改后代码比修改前代码运行比较快，但都需花长时间计算

与其他筛法对比，虽然非最优算法，但由衷感谢小学数学老师给予的思路

本人为业余爱好者，代码粗略编写，若有更好的算法，可以在评论区分享