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例题（一） 输入一个正整数判断是不是素数》对你有帮助，请点赞、收藏，并留下你的观点哦！