【算法基础：数学知识】4.1 质数

**算法基础：数学知识**

**4.1 质数**

质数是指大于1 的自然数，除了1 和自身之外，没有其他正整数能整除它。例如，2、3、5、7 等都是质数。

###4.1.1 质数的定义一个数如果只有一对不同的正因数（即1 和本身），则称该数为质数。

###4.1.2 质数的性质* 每个数都有唯一的一个质因数分解。
*任何两个不同质数的乘积都是一个合数，而不是质数。
*除1 和本身外，任何数都可以被至少一个质数整除。

###4.1.3 质数的检测检测质数有多种方法，我们可以使用以下几种算法：

####1. 判断是否能被小于其平方根的数字整除这是最简单的一种方法。我们只需要检查这个数能否被从2 到它本身（不包括它本身）的所有数字整除。如果不能，则该数一定是质数。

def is_prime(n):
 if n <=1:
 return False for i in range(2, int(n **0.5) +1):
 if n % i ==0:
 return False return True# 测试print(is_prime(25)) # Falseprint(is_prime(23)) # True

def sieve_of_eratosthenes(n):
 primes = [True] * (n +1)
 primes[0] = primes[1] = False for i in range(2, int(n **0.5) +1):
 if primes[i]:
 for j in range(i * i, n +1, i):
 primes[j] = False return [i for i in range(2, n +1) if primes[i]]

# 测试print(sieve_of_eratosthenes(30)) # [2,3,5,7,11,13,17,19,23,29]

import randomdef miller_rabin(n, k=5):
 if n < 2:
 return False for p in [2,3,5,7,11,13,17,19,23,29]:
 if n % p ==0:
 return n == p r, s =0, n -1 while s %2 ==0:
 r +=1 s //=2 for _ in range(k):
 a = random.randrange(2, n -1)
 x = pow(a, s, n)
 if x ==1 or x == n -1:
 continue for _ in range(r -1):
 x = pow(x,2, n)
 if x == n -1:
 break else:
 return False return True# 测试print(miller_rabin(25)) # Falseprint(miller_rabin(23)) # True