python实现aks素数检验法
时间: 2023-03-26 11:03:51 浏览: 104
可以使用Python实现AKS素数检验法,以下是一个简单的实现代码:
```python
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == or n % 3 == :
return False
i = 5
while i * i <= n:
if n % i == or n % (i + 2) == :
return False
i += 6
return True
def gcd(a, b):
if b == :
return a
return gcd(b, a % b)
def power_mod(a, n, p):
res = 1
a = a % p
while n > :
if n % 2 == 1:
res = (res * a) % p
n = n // 2
a = (a * a) % p
return res
def aks(n):
if n == 2 or n == 3:
return True
if is_prime(n) == False:
return False
r = 2
while r <= n:
if gcd(r, n) != 1:
return False
if power_mod(r, n, n) != r % n:
return False
r += 1
return True
```
这个实现代码可以判断一个数是否为素数,如果是素数则返回True,否则返回False。