16 - 数之吟唱：素数
本帖最后由 鱼C-小师妹 于 2021-9-7 14:41 编辑在线视频：
https://www.bilibili.com/video/BV1HT4y1K7DY?p=18
https://xxx.ilovefishc.com/forum/202105/31/204333obvdca8ankppcn9v.png.thumb.jpg
素数相信很多鱼油都不陌生啦，这一讲我们来看如何找出自定义范围内的素数。
算啦，素数概念还是要说下：
只能被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 开始，直到约束条件 m1/2 为止。
为什么到 m1/2 而不是 end 就可以了呢？！
这就要涉及到另一种数：“合数”，它是指在大于 1 的整数中除了能被 1 和本身整除外，还能被其他数（0 除外）整除的数。
而合数可以拆成两个因数相乘，这两个因数一定一个小于等于(和数)1/2，一个大于等于(和数)1/2。
（注：m1/2 即对 m 开根号）
这个理论就不在课堂上证明了，肯定没问题～
就拿 16 举例子，(16)1/2 为 4，所有因子相乘情况：
2 * 8
4 * 4
8 * 2
如果是非素数 m ，那么在 m1/2 前一定存在一个被除数，就没必要继续往下循环咯～
用 i 依次去除需要判定的整数 m，如果 m 能够被 2～ m1/2 中的任何一个整数所整除。
可以确定当前的整数 m 不是素数，因此应提前结束该次循环。
如果 m 不能被 2 ～ m1/2 中的任何一个整数所整除，就表示 m 是素数。
我们还可以创建个标志位 flag 来监控内外循环执行的情况。
将 flag 初值设为 1，在内层循环中判断时，如果 m 能够被 2 ～ m1/2 中的任何一个整数所整除，则在内循环中将 flag 设置为 0 。
如果 m 不能被 2 ～ m1/2 中的任何一个整数所整除，则在内循环中不会修改 flag 标志的值，退出内循环后它的值仍为 1。
此时在外循环中对 flag 的值进行判断，如果 flag=0，则显然当前的 m 不是素数。
如果 flag=1，则当前的 m 是素数，应该将其打印出来。
还需要注意的是，在外循环中，每次要进行下一次迭代之前，要先将 flag 标志再次置为 1。
在设计算法时我们还可以定义 count 变量用来保存最后求得的 start～end 之间素数的总个数。
将上面的算法转成流程图（自己去画，然后来对答案哈）：
**** Hidden Message *****
俗话说得好：
做好流程图，程序立刻出～
先来搞定输入 start 和 end 并判断输入是否合法。
输入 start 和 end 值，并使用 while 语句来判断 start 和 end 的值是否满足条件 start>0 且 start<end 。
如果满足则输入范围合法，否则重新输入：
print("请输入一个整数范围(起start-终end): ")
start = int(input("start = "))
end = int(input("end = "))
while not (start > 0 and start < end):
print("输入的参数有误！快给我重新输入：")
start = int(input("start ="))
end = int(input("end = "))
现在来进入核心阶段求素数，一开始说了使用双循环求指定范围内的素数。
外层循环，对 start～end 之间的每个数进行迭代，检查是否为素数：
m = start
while m <= end:
k = math.sqrt(m)
i = 2
while i <= k:
# 内层循环
i += 1
m += 1
使用 math.sqrt() 方法需要导入 math 模块：
import math
内层循环，判断 2～k 之间的每个数是否能被 m 整除。
若存在一个数能被 m 整除，则跳出内层循环。
否则，m 是素数，打印 m：
while i <= k:
if m % i == 0:
flag = 0
break
i += 1
打印的数字如果很多，我们还是要换行处理，那就 16 个来换行一次：
if flag == 1:
print(m, end=" ")
count += 1
if count % 16 == 0:
print()
flag = 1
m += 1
核心代码都搞定啦，完整代码就是你们的课后作业啦。
源码：
就酱紫，下课！ {:5_105:} {:7_146:} 小师妹，加油哦
{:5_95:} OK，打酱油来啦 我爱鱼c {:5_102:} count = 0
start = int(input('指定开始的数：'))
stop = int(input('指定结束的数：'))
for i in range(start,stop+1):
for n in range(2,i):
ifi % n == 0:
break
else:
if count % 6 == 0:
print( )
else:
print(',',end='')
print(f"{i}是素数",end='')
count += 1
print(f'\n{start}到{stop}之间共有{count}个素数') 。。
{:5_90:} {:10_254:} a # 题干
# 判定一个整数 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}个素数')
沙发 学习一下下 学习
页:
[1]