16 - 数之吟唱：素数

鱼C-小师妹

在线视频：

                               
登录/注册后可看大图

素数相信很多鱼油都不陌生啦，这一讲我们来看如何找出自定义范围内的素数。

算啦，素数概念还是要说下：

只能被1和它自身整除的整数

判定一个整数 a 是否为素数的关键，就是要判定整数 a 能否能被除 1 和它自身以外的其他任何整数所整除。

若都不能整除，则 a 为素数。

这次我们求的是给定范围 start～end 之间的所有素数。

考虑学到这一讲的童鞋能力都有所提升，我们就从程序通用性角度来设计算法。

既然是自定义范围，那就需要从键盘输入 start 和 end 的值。

例如输入 start=1，end=2333，则所编写的程序应能够打印出1～2333 之间的所有素数。

那种直觉应该有了，像这种找数字的题，往往都会用到“n 层循环结构”。

还记得我们在百钱百鸡优化循环的操作吗。

利用条件间的相互关系缩小不同层级间的循环范围。

既然我们考虑用双层循环结构实现，外层循环对 start～end 之间的每个数进行迭代，逐一检查其是否为素数。

外层循环的循环变量用变量 m 表示，m 即代表当前需要进行判断的整数，显然其取值范围为 start≤m≤end 。

内层循环稍显复杂，完成的功能是判断当前的 m 是否为素数。  

我们可以设内循环变量为 i，程序设计时 i 从 2 开始，直到约束条件 m^1/2 为止。

为什么到 m^1/2 而不是 end 就可以了呢？！

这就要涉及到另一种数：“合数”，它是指在大于 1 的整数中除了能被 1 和本身整除外，还能被其他数（0 除外）整除的数。

而合数可以拆成两个因数相乘，这两个因数一定一个小于等于(和数)^1/2，一个大于等于(和数)^1/2。
（注：m^1/2 即对 m 开根号）

这个理论就不在课堂上证明了，肯定没问题～

就拿 16 举例子，(16)^1/2 为 4，所有因子相乘情况：

1. 2 * 8
   
2. 4 * 4
   
3. 8 * 2

复制代码

如果是非素数 m ，那么在 m^1/2 前一定存在一个被除数，就没必要继续往下循环咯～

用 i 依次去除需要判定的整数 m，如果 m 能够被 2～ m^1/2 中的任何一个整数所整除。

可以确定当前的整数 m 不是素数，因此应提前结束该次循环。

如果 m 不能被 2 ～ m^1/2 中的任何一个整数所整除，就表示 m 是素数。

我们还可以创建个标志位 flag 来监控内外循环执行的情况。

将 flag 初值设为 1，在内层循环中判断时，如果 m 能够被 2 ～ m^1/2 中的任何一个整数所整除，则在内循环中将 flag 设置为 0 。

如果 m 不能被 2 ～ m^1/2 中的任何一个整数所整除，则在内循环中不会修改 flag 标志的值，退出内循环后它的值仍为 1。

此时在外循环中对 flag 的值进行判断，如果 flag=0，则显然当前的 m 不是素数。

如果 flag=1，则当前的 m 是素数，应该将其打印出来。

还需要注意的是，在外循环中，每次要进行下一次迭代之前，要先将 flag 标志再次置为 1。

在设计算法时我们还可以定义 count 变量用来保存最后求得的 start～end 之间素数的总个数。

将上面的算法转成流程图（自己去画，然后来对答案哈）：

游客，如果您要查看本帖隐藏内容请回复

俗话说得好：

做好流程图，程序立刻出～

先来搞定输入 start 和 end 并判断输入是否合法。

输入 start 和 end 值，并使用 while 语句来判断 start 和 end 的值是否满足条件 start>0 且 start<end 。

如果满足则输入范围合法，否则重新输入：

1. print("请输入一个整数范围(起start-终end): ")
   
2. start = int(input("start = "))
   
3. end = int(input("end = "))
   
4. while not (start > 0 and start < end):
   
5.     print("输入的参数有误！快给我重新输入：")
   
6.     start = int(input("start ="))
   
7.     end = int(input("end = "))

复制代码

现在来进入核心阶段求素数，一开始说了使用双循环求指定范围内的素数。

外层循环，对 start～end 之间的每个数进行迭代，检查是否为素数：

1. m = start
   
2. while m <= end:
   
3.     k = math.sqrt(m)
   
4.     i = 2
   
5.    while i <= k:
   
6.         # 内层循环
   
7.         i += 1
   
8.     m += 1

复制代码

使用 math.sqrt() 方法需要导入 math 模块：

1. import math

复制代码

内层循环，判断 2～k 之间的每个数是否能被 m 整除。

若存在一个数能被 m 整除，则跳出内层循环。

否则，m 是素数，打印 m：

1. while i <= k:
   
2.         if m % i == 0:
   
3.             flag = 0
   
4.             break
   
5.         i += 1

复制代码

打印的数字如果很多，我们还是要换行处理，那就 16 个来换行一次：

1. if flag == 1:
   
2.         print(m, end=" ")
   
3.         count += 1
   
4.         if count % 16 == 0:
   
5.             print()
   
6.     flag = 1
   
7.     m += 1

复制代码

核心代码都搞定啦，完整代码就是你们的课后作业啦。



源码： p16.py.zip (857 Bytes, 下载次数: 12, 售价: 8 鱼币)

2021-7-27 19:18 上传

点击文件名下载附件

就酱紫，下课！

小月yyds

柿子饼同学

李姐万岁

小师妹，加油哦

hornwong

jinhuaedu

OK，打酱油来啦

Debug007

我爱鱼c

LyyLD

游刃鱿鱼

1. count = 0
   
2. start = int(input('指定开始的数：'))
   
3. stop = int(input('指定结束的数：'))
   
4. for i in range(start,stop+1):
   
5.     for n in range(2,i):
   
6.         if  i % n == 0:
   
7.             break
   
8.     else:
   
9.         if count % 6 == 0:
   
10.             print( )
    
11.         else:
    
12.             print(',',end='')
    
13.         print(f"{i}是素数",end='')
    
14.         count += 1
    
15. 
    
16. 
    
17. print(f'\n{start}到{stop}之间共有{count}个素数')

复制代码

tucc

。。

张亚当

CG2022

投入就放过

a

Hyjxsssss

# 题干
# 判定一个整数 a 是否为素数的关键，就是要判定整数 a 能否能被除 1 和它自身以外的其他任何整数所整除。
# 这次我们求的是给定范围 start～end 之间的所有素数

# 首先判断一个数字是不是素数
# 再外层叠加循环

start = int(input('start = '))
end = int(input('end = '))
print('%d - %d 中的素数为：' % (start, end))
count = 0
for n in range(start, end + 1):
    factorstorage = []
    for i in range(2, n):
        if n%i == 0:
            factorstorage.append(i)
            break
    if len(factorstorage) == 0:
        count += 1
        if count%5 != 0:
            print(n, '\t', end = '')
        else:
            print(n)
print('\n经统计 %d - %d 中共有 %d 个素数' % (start, end, count))

语与余

import math
count = 0
start = int(input('start的数值：'))
end = int(input('end的数值：'))
for i in range(start,end+1):
    for j in range(2,int(math.sqrt(i))+1):
        if i % j == 0:
            break
    else:
        count +=1
        print(i,end=' ')
        if count % 16 == 0:
            print()
print(f'\n总共有{count}个素数')
   

Alexiiis

沙发

pingkong

学习一下下

wk012233

学习