【蓝桥杯学习笔记】3. 质数判断

系列文章目录

【蓝桥杯学习笔记】1. 入门基本语法及练习题

【蓝桥杯学习笔记】2. 常用模型----最大公约数和最小公倍数


文章目录


前言

        蓝桥本笔记-----从入门到放弃

        本片文章使用Python语言编写----Now is better than never


-

一、质数判断

1.质数:
 在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数,即不能被如何数整除  

     由于自然数中大于2的偶数至少能被2整除所以不是质数,且只要取3~sqrt(x)+1 范围内的数判断是否可以整除即可,因此代码可以写成:

import math
def isPrime(x):
    if x == 2:
        return True
    elif x % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(x)) + 1, 2):
        if x % i == 0:
            return False
    return True

   又由阴性合数定理和阴性素数定理
            大于3的素数只分布在6n-1和6n+1两数列中。(6n-1和6n+1两数列中不只包含了质数)
    然而 任何一个自然数,总可以表示成以下六种形式之一:
    6n,6n+1,6n+2,6n+3,6n+4,6n+5(n=0,1,2...)
    因此代码可以写成:

def  isPrime(x):
    if x == 2 or (x == 3):
        return True
    elif (x%6 != 1) and (x%6 != 5):
        return False
    for i in range(5, int(math.sqrt(x)) + 1, 6):
        if x % i == 0 or (x % (i + 2) == 0):
            return False
    return True

总结

代码模板:

def  isPrime(x):
    if x == 2 or (x == 3):
        return True
    elif (x%6 != 1) and (x%6 != 5):
        return False
    for i in range(5, int(math.sqrt(x)) + 1, 6):
        if x % i == 0 or (x % (i + 2) == 0):
            return False
    return True

 参考链接:【Python】质数的几种判断方法 - 知乎 (zhihu.com)

上一篇:约瑟夫问题链表解决


下一篇:纪念日计时器