鱼C论坛

 找回密码
 立即注册
查看: 5882|回复: 17

[技术交流] 16 - 数之吟唱:素数

[复制链接]
发表于 2021-7-24 17:59:59 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 鱼C-小师妹 于 2021-9-7 14:41 编辑

在线视频:




                               
登录/注册后可看大图


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

算啦,素数概念还是要说下:

只能被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 之间素数的总个数。

将上面的算法转成流程图(自己去画,然后来对答案哈):

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


俗话说得好:

做好流程图,程序立刻出~

先来搞定输入 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
核心代码都搞定啦,完整代码就是你们的课后作业啦。

2021-07-27_19-16-31.jpg

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

就酱紫,下课!

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-7-24 18:53:12 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-7-24 20:46:13 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-7-24 22:18:02 | 显示全部楼层
小师妹,加油哦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-7-25 21:32:09 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-8-24 15:26:30 | 显示全部楼层
OK,打酱油来啦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-9-17 09:49:57 | 显示全部楼层
我爱鱼c
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-11-4 14:47:34 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-11-9 16:46:21 | 显示全部楼层
count = 0
start = int(input('指定开始的数:'))
stop = int(input('指定结束的数:'))
for i in range(start,stop+1):
    for n in range(2,i):
        if  i % n == 0:
            break
    else:
        if count % 6 == 0:
            print( )
        else:
            print(',',end='')
        print(f"{i}是素数",end='')
        count += 1


print(f'\n{start}到{stop}之间共有{count}个素数')
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-1-5 20:29:56 | 显示全部楼层
。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-2-18 03:04:20 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-3-9 20:36:28 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-3-16 14:28:03 | 显示全部楼层
a
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-5-9 13:31:24 | 显示全部楼层
# 题干
# 判定一个整数 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))
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-14 19:16:20 | 显示全部楼层
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}个素数')
   
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-6-5 22:21:25 | 显示全部楼层
沙发
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-11-2 09:19:39 | 显示全部楼层
学习一下下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-11-2 14:48:42 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-15 01:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表