栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

866. 试除法判定质数(python)

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

866. 试除法判定质数(python)

866. 试除法判定质数(python)

文章目录
  • 866. 试除法判定质数(python)
    • 题目
    • 解法
    • python代码实现

题目

解法

质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。与之相对的是质数,而1既不属于质数也不属于合数。

方法一 : 暴力破解 , 时间复杂度是 O(n)。

方法二:由合数的约数总是成对出现,如,2是6的约数,6/2 = 3,那3也是6的约数 。
可以得出更一般的推导式,若d|n,令a = d|n,则有a|n成立。我们只枚举d <= d|n这部分数,也就是d<=sqrt(n)。

方法二的时间复杂度为O(sqrt(n)),空间复杂度为O(1)。

python代码实现
def judge(n):
    if n <= 1:
        return False
    i = 2
    while i <= n // i:
        if n % i == 0:
            return False
        i += 1
    return True


for _ in range(int(input())): # int(input()) 只能接受数字, 并且转换成int类型的数据
    n = int(input())
    print("Yes") if judge(n) else print("No")

注:
上述代码中 while i <= n // i 的循环条件,最好不要写成 while i*i<=n,当n = 2147483647 时,此时若 i 2 ≤ n i^2 leq n i2≤n,但是在后面的循环中存在溢出风险。也不推荐写成while i<=sqrt(n),每次循环都需要求一个根号n,计算根号比较慢。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/889442.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号