python巧用定理判断素数

判断一个数n是否是素数

求一个数的素因数个数

求大于等于指定数的最小素数

在数论中有三个非常重要的关于素数的定理

1、任何数都可以表示成若干个素数的乘积

2、任意数的素因子一个大于根号n的自然数，另一个与其对应的因子则必小于根号n。

3、除了2和3以外的所有素数都是6k±1型（k=1、2、3、...），这里要反过来是不成立的，也就是说6k±1型的不一定都是素数，例如35是6k-1型，但它不是素数

判断一个数n是否是素数

方法1：遍历从2到n-1的所有因子，时间复杂度 $O(n)$

def is_prime(n):if n < 2:    # 小于2的肯定不是素数return 0for i in range(2, n):if n % i == 0:    #如果存在2到n的因子，则不是素数return 0return 1    #如果2到n遍历完后都没有，则是素数

方法2：使用性质2，我们其实可以只遍历从2到根号n，此时时间复杂度降为 $O(\sqrt{n})$

def is_prime(n):if n < 2:    # 小于2的肯定不是素数return 0for i in range(2, int(n**0.5)+1):    #这里int会向下取整，所以加1消除误差if n % i == 0:   return 0return 1

方法3：使用性质2和性质3，从2到根号n，然后每隔6个数遍历，此时时间复杂度降为 $O(\frac{1}{6}\sqrt{n})$

def is_prime(n):if n < 2: return 0if n <= 3:  # 2或3肯定是素数return 1if n % 2 == 0 or n % 3 == 0:    # 如果能整除2或3，则不是素数return 0for i in range(5, int(n ** 0.5) + 1, 6):#从5开始，步长为6if n % i == 0 or n % (i + 2) == 0:    # i表示6k-1，i+2表示6k+1return 0return 1

求一个数的素因数个数

根据定理1，任意数都可以表示为若干个素数的乘积，写一个程序，要求计算一个数的素因子个数

题目链接

https://www.lanqiao.cn/problems/2155/learning/?page=1&first_category_id=1&sort=students_count&category_id=3&name=%E8%B4%A8%E5%9B%A0%E6%95%B0

ans = 0
n = int(input())
# 2和3单独讨论
for i in [2, 3]:if n % i == 0:  # 如果可以整除i，即含有素因子ians = ans + 1  # 计数加1while n % i == 0:  # 将n一直除以i，直到n中没有因子in = n // ifor i in range(5, int(n ** 0.5) + 1, 6):  for j in [i, i + 2]:  # j分别表示6k-1和6k+1# 以下过程与上面同理if n % j == 0:ans = ans + 1while n % j == 0:n = n // jif n != 1:  # 如果最后除出来结果不是1，说明还剩个素因数，还需要再加1ans = ans + 1print(ans)

输入396，结果为3，因为396有2、3、11三个素因子

求大于等于指定数的最小素数

def is_prime(n):if n < 2:return 0if n <= 3:return 1if n % 2 == 0 or n % 3 == 0:return 0for i in range(5, int(n ** 0.5) + 1, 6):if n % i == 0 or n % (i + 2) == 0:return 0return 1n = int(input())if is_prime(n):  # 如果是素数则直接输出print(n)
else:for j in range(1, 7):  # 根据性质，最多隔6位肯定会有素数，所以一直给n加1，直到n是素数则输出n = n + 1if is_prime(n):print(n)break

输入17