Python例题（一） 输入一个正整数判断是不是素数
147 浏览量
2020-12-22
11:20:19
上传
评论 4
收藏 49KB PDF 举报
Python例题（一）例题（一） 输入一个正整数判断是不是素数输入一个正整数判断是不是素数
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:
break
if x == number:
print (number,'是素数')
else:
print (number,'不是素数')
else:
print('?请输入正整数???还要大于2?')
2. 进行初步优化，合理利用特点来计算进行初步优化，合理利用特点来计算
合数必定可拆分成两个非1的约数，其中一个小于该数的平方根，另一个大于该数的平方根。
用用for和和break
import math
m = int (input('请输入一个大于一的整数：'))
k = int (math.sqrt(m))
for i in range(2,k+2):
if m % i == 0:
break
if i == k+1:
print (m,'是素数')
else:
print (m,'不是素数')
用用while和和bool
import math
m = int(input ('请输入一个大于1的正整数：'))
n = int (math.sqrt(m))
flag = True
i = 2
while i <= n and flag == True:
if (m / i == 0 ):
flag = False
else:
i += 1
评论0