马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 鱼C-小师妹 于 2021-9-7 14:41 编辑
在线视频:
素数相信很多鱼油都不陌生啦,这一讲我们来看如何找出自定义范围内的素数。
算啦,素数概念还是要说下:
判定一个整数 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,所有因子相乘情况:
如果是非素数 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 之间素数的总个数。
将上面的算法转成流程图(自己去画,然后来对答案哈):
俗话说得好:
先来搞定输入 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 模块:
内层循环,判断 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
核心代码都搞定啦,完整代码就是你们的课后作业啦。
源码:
p16.py.zip
(857 Bytes, 下载次数: 13, 售价: 8 鱼币)
就酱紫,下课! |