python学习：用两种思路计算质数与合数

您所在的位置：网站首页 › python求最小的100个素数 › python学习：用两种思路计算质数与合数

python学习：用两种思路计算质数与合数

2023-08-24 21:17| 来源: 网络整理| 查看: 265

质数（素数）与合数：

合数指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。

与之相对的是质数，质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。而1既不属于质数也不属于合数。最小的合数是4。（因数：如果整数a除以整数b(b≠0) 的商是整数，我们就说b是a的因数。）

计算思路：思路①：

假如要判断一个数字“x”是不是质数，那么根据定义，我们就直接遍历[2，x-1]范围内的的数字“i”，并分别计算每次x%i的结果是否为0，若有一个结果为0，则表明“x”可以被这个“i”整除，即“x”存在除了1和她本身之外的因数，那么x就是合数，反之，就是质数。

代码1.1： x = int(input("请输入要判断的整数")) if x < 2: #质数的范围是[2,+∞） print(x,'不是质数也不是合数') else: for i in range(2,x): #对符合质数范围的进行计算 if x%i == 0: #先判断是否为合数 print(x,'是合数') break else: print(x,'是质数') #剩下的都是质数思路②：

假如一个数c是合数，那么就存在因数a，b（a,b>1)，且axb=c，而axb=c表现在坐标轴上就是一个反比例函数。(即：a=c/b,c是常数)

也就是说：当两个数a，b乘积一定时，a与b的值会呈反比例关系。而：

当a=b时，因为 a x b =c，所以a = b = √￣c

又因为a，b呈反比例关系，所以a，b至少有一个数字会小于或等于根号c。

（简单来说就是：如果axb=c，则a，b至少有个数会小于等于根号c）

因此,只要小于或等于根号c的数不能整除c。则c一定是质数（这里的“数”排除1）。

那么，于是，就有了第二种思路的（对比第一段代码，加入了一行新代码和修改了一处的取值）：

代码2.1 x = int(input("请输入要判断的整数")) if x < 2: print(x,'不是质数也不是合数') else: x2=int(x**0.5) #求出根号x，并向下取整 for i in range(2,x2+1): #int向下取整了，末尾要 +1 if x%i == 0: print(x,'是合数') break else: print(x,'是质数')

看起来第二种思路似乎会比第一种思路减少了一半的计算量，我们慢慢丰富代码，最后比一下两种方式的计算时间吧。

丰富代码： 1、加入循环，使得用户可以重复提交想要判断的数字

思路①更改后：

代码1.2 x = int(input("请输入要判断的整数")) y=x #配合while达成循环 while x == y: #让程序能不停的循环，不知道有没有更好的方法···· if x < 2: print(x,'不是质数也不是合数') else: for i in range(2,x): if x%i == 0: print(x,'是合数') break else: print(x,'是质数') x = int(input("请输入要判断的整数")) #每次输出结果后，用户可以再次输入数据并运行 y=x #配合上面的while达成循环···

思路②更改后：

代码2.2 x = int(input("请输入要判断的整数")) y=x while x == y: if x < 2: print(x,'不是质数也不是合数') else: x2=int(x**0.5) for i in range(2,x2+1): if x%i == 0: print(x,'是合数') break else: print(x,'是质数') x = int(input("请输入要判断的整数")) y=x 2、直接设置一个区间，让程序算出指定区间内的所有质数和因数（省去了重复输入数字的过程）

思路①修改后：

代码1.3 a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) for x in range(a,b+1): if x < 2: #以下是照抄代码1.1, print(x, '不是质数也不是合数') else: for i in range(2, x): if x % i == 0: print(x, '是合数') break else: print(x, '是质数')

思路②修改后：

代码2.3 a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) for x in range(a,b+1): #以下照抄2.1 if x < 2: print(x, '不是质数也不是合数') else: x2 = int(x ** 0.5) for i in range(2, x2 + 1): if x % i == 0: print(x, '是合数') break else: print(x, '是质数') 3、在“2”的基础上，统计区间内质数合数的数量：

思路①修改后：

代码1.3.1 a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) c = 0 #变量c用于记录合数数量 d = 0 #变量d用于记录质数数量 for x in range(a,b+1): if x < 2: print(x, '不是质数也不是合数') else: for i in range(2, x): if x % i == 0: print(x, '是合数') c+=1 #c记录合数 break else: print(x, '是质数') d+=1 #d记录质数 print('程序结束,[{}，{}]之间共有{}个合数{}个质数'.format(a,b,c,d))

思路②修改后：

代码2.3.1 a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) c=0 d=0 for x in range(a,b+1): if x < 2: print(x, '不是质数也不是合数') else: x2 = int(x ** 0.5) for i in range(2, x2 + 1): if x % i == 0: print(x, '是合数') c+=1 break else: print(x, '是质数') d+=1 print('程序结束,[{}，{}]之间共有{}个合数{}个质数'.format(a,b,c,d))

2.3.1实例：

PyDev console: starting. Python 3.8.3 (default, Jul 2 2020, 17:30:36) [MSC v.1916 64 bit (AMD64)] on win32 >>> runfile('D:/pycharm/practise/质数合数.py', wdir='D:/pycharm/practise') 请输入区域下限>? 1 请输入区域上限>? 10 1 不是质数也不是合数 2 是质数 3 是质数 4 是合数 5 是质数 6 是合数 7 是质数 8 是合数 9 是合数 10 是合数程序结束,[1，10]之间共有5个合数4个质数 4、在“3”的基础上，用列表记录每个数字，用户可选择是否查看

在以上（1.3.1和2.3.1）代码运行的过程中，用户必须看完每一个“x是质数/合数”后才可知道区域内总共有几个质数/合数，我想去掉这些“print”过程，取而代之的是运算结束后用户自己选择是否查看区域内哪些数字是质数/合数。

思路①修改：

代码1.3.2 a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) c = 0 d = 0 e = [] #列表e记录合数 f = [] #列表f记录质数 for x in range(a,b+1): if x < 2: continue else: for i in range(2, x): if x % i == 0: c+=1 e.append(x) #e列表储存合数 break else: d+=1 f.append(x) #f列表储存质数 print('程序结束,[{}，{}]之间共有{}个合数{}个质数'.format(a,b,c,d)) print('输入“质数”查看所有质数，输入“合数”查看所有合数') watch=input("请输入要查看的数据类型：") while watch != '结束程序': #一下子想不到别的循环办法、、、 if watch == '质数': print("[{}，{}]之间的质数有：".format(a,b),e) elif watch == '合数': print("[{}，{}]之间的合数有：".format(a,b),f) else: print('[{}，{}]之间共有{}个合数{}个质数'.format(a, b, c, d)) print('输入“质数”查看所有质数，输入“合数”查看所有合数') watch = input("请输入要查看的数据类型：")

思路②修改后：

代码2.3.2 a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) c=0 d=0 e = [] #列表e记录合数 f = [] #列表f记录质数 for x in range(a,b+1): if x < 2: continue else: x2 = int(x ** 0.5) for i in range(2, x2 + 1): if x % i == 0: c+=1 e.append(x) #e列表储存合数 break else: d+=1 f.append(x) #f列表储存质数 print('程序结束,[{}，{}]之间共有{}个合数{}个质数'.format(a,b,c,d)) print('输入“质数”查看所有质数，输入“合数”查看所有合数') watch=input("请输入要查看的数据类型：") while watch != '结束程序': if watch == '质数': print("[{}，{}]之间的质数有：".format(a,b),e) elif watch == '合数': print("[{}，{}]之间的合数有：".format(a,b),f) else: print('[{}，{}]之间共有{}个合数{}个质数'.format(a, b, c, d)) print('输入“质数”查看所有质数，输入“合数”查看所有合数') watch = input("请输入要查看的数据类型：") 5、在“4”的基础上，让用户可以选择输出该区域的前N个质数/因数：

比如，有时候可能想找（1,100）的前10个质数······之类的

思路①修改后：

代码1.3.3 a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) xcc = 0 xdd = 0 c = 0 d = 0 e = [] f = [] for x in range(a, b + 1): if x < 2: continue else: for i in range(2, x): if x % i == 0: c += 1 e.append(x) break else: d += 1 f.append(x) print('程序结束,[{}，{}]之间共有{}个合数{}个质数'.format(a,b,c,d)) print('输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引') watch=input("请输入要查看的数据类型：") while watch != '结束程序': if watch == '质数': print("[{}，{}]之间的质数有：".format(a,b),e) elif watch == '合数': print("[{}，{}]之间的合数有：".format(a,b),f) elif watch == '索引': #主要是加了这里的东西 suoh = int(input("索引前几个合数？")) suoz = int(input("索引前几个质数？")) print("前{}个因数是：".format(suoh),e[:suoh]) print("前{}个质数是：".format(suoz),f[:suoz]) else: print('[{}，{}]之间共有{}个合数{}个质数'.format(a, b, c, d)) print('输入“质数”查看所有质数，输入“合数”查看所有合数') watch = input("请输入要查看的数据类型：")

思路②修改后：

代码2.3.3 a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) c=0 d=0 e = [] f = [] for x in range(a,b+1): if x < 2: continue else: x2 = int(x ** 0.5) for i in range(2, x2 + 1): if x % i == 0: c+=1 e.append(x) break else: d+=1 f.append(x) print('程序结束,[{}，{}]之间共有{}个合数{}个质数'.format(a,b,c,d)) print('输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引') watch=input("请输入要查看的数据类型：") while watch != '结束程序': if watch == '质数': print("[{}，{}]之间的质数有：".format(a,b),e) elif watch == '合数': print("[{}，{}]之间的合数有：".format(a,b),f) elif watch == '索引': #主要是加了这里的东西 suoh = int(input("索引前几个合数？")) suoz = int(input("索引前几个质数？")) print("前{}个因数是：".format(suoh),e[:suoh]) print("前{}个质数是：".format(suoz),f[:suoz]) else: print('[{}，{}]之间共有{}个合数{}个质数'.format(a, b, c, d)) print('输入“质数”查看所有质数，输入“合数”查看所有合数') watch = input("请输入要查看的数据类型：")

代码2.3.3实例：

PyDev console: starting. Python 3.8.3 (default, Jul 2 2020, 17:30:36) [MSC v.1916 64 bit (AMD64)] on win32 >>> runfile('D:/pycharm/practise/质数合数.py', wdir='D:/pycharm/practise') 请输入区域下限>? 1 请输入区域上限>? 1000 程序结束,[1，1000]之间共有831个合数168个质数输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引请输入要查看的数据类型：>? 索引索引前几个合数？>? 10 索引前几个质数？>? 10 前10个因数是： [4, 6, 8, 9, 10, 12, 14, 15, 16, 18] 前10个质数是： [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 请输入要查看的数据类型： 6、添加一个简单的计算“计算过程耗时”的功能

思路①修改后

代码1.3.4 import time ts=time.perf_counter() a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) xcc = 0 xdd = 0 c = 0 d = 0 e = [] f = [] for x in range(a, b + 1): if x < 2: continue else: for i in range(2, x): if x % i == 0: c += 1 e.append(x) break else: d += 1 f.append(x) te=time.perf_counter() t=te-ts print('程序结束,[{}，{}]之间共有{}个合数{}个质数,耗时{:.2f}s'.format(a,b,c,d,t)) print('输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引') watch=input("请输入要查看的数据类型：") while watch != '结束程序': if watch == '质数': print("[{}，{}]之间的质数有：".format(a,b),e) elif watch == '合数': print("[{}，{}]之间的合数有：".format(a,b),f) elif watch == '索引': suoh = int(input("索引前几个合数？")) suoz = int(input("索引前几个质数？")) print("前{}个因数是：".format(suoh),e[:suoh]) print("前{}个质数是：".format(suoz),f[:suoz]) else: print('[{}，{}]之间共有{}个合数{}个质数,耗时{:.2f}s'.format(a,b,c,d,t)) print('输入“质数”查看所有质数，输入“合数”查看所有合数') watch = input("请输入要查看的数据类型：")

思路②修改后

代码2.3.4 import time ts=time.perf_counter() a = int(input("请输入区域下限")) b = int(input("请输入区域上限")) c=0 d=0 e = [] f = [] for x in range(a,b+1): if x < 2: continue else: x2 = int(x ** 0.5) for i in range(2, x2 + 1): if x % i == 0: c+=1 e.append(x) break else: d+=1 f.append(x) te=time.perf_counter() t=te-ts print('程序结束,[{}，{}]之间共有{}个合数{}个质数,耗时{:.2f}s'.format(a,b,c,d,t)) print('输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引') watch=input("请输入要查看的数据类型：") while watch != '结束程序': if watch == '质数': print("[{}，{}]之间的质数有：".format(a,b),e) elif watch == '合数': print("[{}，{}]之间的合数有：".format(a,b),f) elif watch == '索引': suoh = int(input("索引前几个合数？")) suoz = int(input("索引前几个质数？")) print("前{}个因数是：".format(suoh),e[:suoh]) print("前{}个质数是：".format(suoz),f[:suoz]) else: print('[{}，{}]之间共有{}个合数{}个质数,耗时{:.2f}s'.format(a,b,c,d,t)) print('输入“质数”查看所有质数，输入“合数”查看所有合数') watch = input("请输入要查看的数据类型：") 比较两种思路快慢

最后用的是代码1.3.4和2.3.4来进行比较，用的范围是[1,50000]

1.3.4战绩： 2.3.4战绩：

27.26s 6.28s

30.04s 4.82s

25.14s 4.91s

26.47s 4.32s

27.01s 3.20s

这2.3.4的战绩一度让我怀疑我是不是在输入范围时少按了一个“0”，两个思路各测试了五次后，毫无疑问，用第二种思路去算，更快，而且快了好多倍。

而后，我又测试了1.3.4算一到十万和2.3.4算一到一百万：

请输入区域下限>? 1 请输入区域上限>? 100000 #十万程序结束,[1，100000]之间共有90407个合数9592个质数,耗时100.15s 输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引请输入要查看的数据类型：请输入区域下限>? 1 请输入区域上限>? 1000000 #一百万程序结束,[1，1000000]之间共有921501个合数78498个质数,耗时24.56s 输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引请输入要查看的数据类型：

·······可见，计算所用的思路不同，对于计算速度的影响很大。

最后，玩了亿下（并没有到亿）：

请输入区域下限>? 1 请输入区域上限>? 3000000 #三百万程序结束,[1，3000000]之间共有2783183个合数216816个质数,耗时65.59s 输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引请输入要查看的数据类型：请输入区域下限>? 1 请输入区域上限>? 4000000 #四百万程序结束,[1，4000000]之间共有3716853个合数283146个质数,耗时85.97s 输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引请输入要查看的数据类型：请输入区域下限>? 1 请输入区域上限>? 5000000 #五百万程序结束,[1，5000000]之间共有4651486个合数348513个质数,耗时135.75s 输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引请输入要查看的数据类型：请输入区域下限>? 1 请输入区域上限>? 10000000 #一千万程序结束,[1，10000000]之间共有9335420个合数664579个质数,耗时321.89s 输入“质数”查看所有质数，输入“合数”查看所有合数，输入“索引”进入索引请输入要查看的数据类型：

碎碎念：1.3.4跑一到10万的时间，2.3.4能跑完一到400多万（100s）

【本文地址】

公司简介

联系我们