素数判断算法（基于python实现）

素数是只能被1与⾃⾝整除的数，根据定义，我们可以实现第⼀种算法。算法⼀：

def isprime(n):

if n < 2: return False

for i in range(2,int(math.sqrt(n))+1): if n % i == 0: return False return True

任意⼀个合数都可分解为素数因⼦的乘积，观察素数的分布可以发现：除 2,3 以外的素数必定分布在 6k (k为⼤于1的整数) 的两侧。6k % 6== 0, (6k+2) % 2== 0,(6k+3) %3==0,(6k+4)%2==0,

所以2,3外的素数形式只能写成 6k+1 或 6k-1的形式。据此，我们可以缩⼩因⼦范围。算法⼆：

def isprime(n):

if n == 2 or n == 3: return True

if n % 2 == 0 or n % 3 == 0: return False

for k in range(6,int(math.sqrt(n)) + 2, 6): if n % (k-1) == 0 or n % (k+1) == 0: return False return True

建⽴⼀个⼤⼩为n的数组，初始值置为真。从2开始设置步长(length)直⾄n的平⽅根，将length*i (i > 1) 的值置为False。这就是埃拉托斯特尼筛法的基本思想。适⽤于筛选⼩于n的所有素数，算法如下：算法三：

def isprime(n):

r = [[i,True] for i in range(1,n+1)] r[0] = [1,False]

for i in range(1,int(math.sqrt(n))): j = i * 2 + 1 while j < len(r): r[j] = [j+1,False] j += i + 1 return r

费马⼩定理: ap-1 = 1 (mod p) ,其中gcd(p,a) = 1 且 p 为素数

p为素数时等式⼀定成⽴，但使等式成⽴的p不⼀定都是素数，但⾮素数p数量极少，称之为伪素数。

任意⼤素数n可写成 n = u * 2t + 1, 其中 t 为 ⼤于1 的整数，u为奇数。a n - 1 = (au)2^t, 求出au 后，连续t次平⽅即可求得。算法四：

def isprime_fourth(n): if n == 2: return True

if n % 2 == 0: return False

# 若n为⼤于2的素数,形式可写成 n=u*(2^t) + 1, t >= 1 and u % 2 == 1 t = 0 u = n - 1

while u % 2 == 0: t += 1 u //= 2

# 随机选择底数，若n为素数，gcd(a,n)==1 a = random.randint(2,n-1)

# 若n为素数，则a^(n-1) % n == 1；先计算 a^u % n，再连续t次平⽅可得 r = pow(a,u,n) if r != 1:

while t > 1 and r != n-1: r = (r*r) % n t -= 1 if r != n - 1:

return False return True