1. 什么是素数与合数
定义
在大于1的整数中,除了1和该数自身外,无法被其他整数整除的数。大于1的数若不为素数,则被称为合数,也叫作合成数。
素数的特点
大于2的质数只能是奇数。(不能说大于2的奇数都是质数。)
大于5的质数,个位数只能是1、3、7、9。(不能说个位数是1、3、7、9的数都是质数。)
大于3的质数只能是6n-1或者6n+1型(n是正整数)。(不能说6n-1或者6n+1型的数都是质数)。
合数的特点
所有大于2的偶数都是合数;所有大于5的奇数中,个位为5的都是合数;除0以外,所有个位为0的自然数都是合数;所有个位为4,6,8的自然数都是合数;最小的(偶)合数为4,最小的奇合数为9;每一个合数都可以以唯一形式被写成质数的乘积,即分解质因数。(算术基本定理)任何一个合数都可以分解为几个质数的乘积1既不是质数,也不是合数。除了2之外,所有的偶数都是合数;除了2之外,所有的质数都是奇数;奇数中,有合数(例如9、15、21等),也有质数(比如3、5、17)。2. 方法介绍
1. 直接比较,虽然最易想到,但效率较低
即暴力搜索,从1到n的数字全部枚举并进行检查.这个方法虽然很容易想到,但是很效率却很低.
用for和break写了一个,while和bool不打算写了,反正下面也有.
number = int (input('请输入一个正整数:'))if number > 2:for x in range (2,number+1):if number % x == 0:breakif x == number:print (number,'是素数')else:print (number,'不是素数')else:print('?请输入正整数???还要大于2?')
2. 进行初步优化,合理利用特点来计算
合数必定可拆分成两个非1的约数,其中一个小于该数的平方根,另一个大于该数的平方根。
用for和break
import mathm = int (input('请输入一个大于一的整数:'))k = int (math.sqrt(m))for i in range(2,k+2):if m % i == 0:breakif i == k+1:print (m,'是素数')else:print (m,'不是素数')
用while和bool
import mathm = int(input ('请输入一个大于1的正整数:'))n = int (math.sqrt(m))flag = Truei = 2while i <= n and flag == True:if (m / i == 0 ):flag = Falseelse:i += 1if (flag == True):print (m ,'素数')else:print(m ,'合数')
3.继续优化,在被测试数逐渐增大时,效率更显著
这个优化是考虑到了质数的另一个特点:大于3的质数只能是6n-1或者6n+1型(n是正整数).
首先 6x 肯定不是质数,因为它能被 6 整除;其次 6x+2 肯定也不是质数,因为它还能被2整除;依次类推,6x+3 肯定能被 3 整除;6x+4 肯定能被 2 整除。那么,就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。所以循环的步长可以设为 6,然后每次只判断 6 两侧的数即可。
import mathm = int (input('请输入一个正整数:'))if m <= 3 and m > 1:print(m,'是素数哦')# 2和3单独处理if m % 6 != 1 and m % 6 != 5:print (m,'不是素数') # 不在6的倍数两侧的一定不是素数else: #在6的倍数 两侧的也仍需判断,判断可以套用第二个方法来进行判断n = int (math.sqrt(m))for i in range(5,n+2,6):if (m % i == 0 or m % (i+2) == 0):breakif i == n + 1:print (m,'是素数')else:print (m,'不是素数')
如果觉得《Python例题(一) 输入一个正整数判断是不是素数》对你有帮助,请点赞、收藏,并留下你的观点哦!