python基础-质数判断及优化

文章目录一、问题描述二、代码三、问题2优化四、数学补充
一、问题描述
1.获取用户输入的任意数,判断其是否是质数。
2.求1000以内所有的质数,并优化程序

质数判断条件:
质数是只能被1和它自身整除的数,1不是质数也不是合数。

二、代码

问题1代码

#方法一
num = int(input('请输入任意输入一个数字:'))
#创建变量num,接收用户输入的参数并转化成整形
i = 0
i = num -1
if num ==1:
print(num,'既不是质数也不是合数。')
elif num 1 and num % i != 0 :
i= i-1
if i ==1:
print (num,'是质数' )
else :
print (num,'是合数' )

#方法二
i = 2
# 创建一个变量,用来记录num是否是质数,默认认为num是质数
num = int(input('请输入任意输入一个数字:'))
flag = True
while i < num:
# 判断num能否被i整除
# 如果num能被i整除,则说明num一定不是质数
if num % i == 0 :
# 一旦进入判断,则证明num不是质数,则需要将flag修改为false
flag = False
i += 1
if flag :
print(num,'是质数')
else :
print(num,'不是质数')

问题2代码

i = 2
while i <= 1000:
# 创建一个变量,记录i的状态,默认认为i是质数
flag = True
# 判断i是否是质数
# 获取所有可能成为i的因数的数
j = 2
while j < i:
# 判断i能否被j整除
if i % j == 0:
# i能被j整除,证明i不是质数,修改flag为False
flag = False
j += 1
# 验证结果并输出
if flag :
print(i)
i += 1

三、问题2优化

优化方案:
模块,通过模块可以对Python进行扩展
引入一个time模块,来统计程序执行的时间
time()函数可以用来获取当前的时间,返回的单位是秒
获取程序开始的时间,以运行时间来衡量优化结果。
优化前:

from time import *
begin = time()
i = 2
while i <= 1000:
# 创建一个变量,记录i的状态,默认认为i是质数
flag = True
# 判断i是否是质数
# 获取所有可能成为i的因数的数
j = 2
while j < i:
# 判断i能否被j整除
if i % j == 0:
# i能被j整除,证明i不是质数,修改flag为False
flag = False
j += 1
# 验证结果并输出
if flag :
pass
#在测试优化中我们不考虑print的影响
# print(i)
i += 1
# 获取程序结束的时间
end = time()
# 计算程序执行的时间
print("程序执行花费了:",end - begin , "秒")
# 程序执行花费了: 0.10073041915893555 秒

优化后程序:

from time import *
begin = time() #获取程序开始时间
i = 2
while i <= 100000:
flag = True
j = 2
while j <= i ** 0.5: #对条件优化 数学逻辑,只用查询一般就可以确定是否为质数。
if i % j == 0:
flag = False
# 一旦进入判断,则证明i一定不是质数,此时内层循环没有继续执行的必要
# 使用break来退出内层的循环
break
j += 1
if flag :
# print(i)
pass
i += 1

# 获取程序结束的时间
end = time()

# 计算程序执行的时间
print("程序执行花费了:",end - begin , "秒")
程序执行花费了: 0.0019943714141845703 秒

执行次数 优化前 优化后时间
1000 0.10073041915893555秒 0.0019943714141845703 秒
10000 10.086509466171265 秒 0.0019943714141845703 秒
100000 无法计算出来 1.2611010074615479 秒

四、数学补充

1.将循环控制条件修改如下:

修改前: j < i
修改后:j <= i ** 0.5
修改原因:在这里插入图片描述
2.while循环添加break修改:
修改原因:质数是只能被1和它自身整除的数。
使用break来退出内层的循环
在这里插入图片描述

作者:f3NWIVKIo@t5

相关推荐

python之字典详解

在这里插入图片描述

python学习第一天—django框架—后台管理

python基础知识学习

在这里插入图片描述

python采集信息+Python预处理+tableau绘制可视化大屏