python的超大素数判断
时间: 2023-11-21 09:58:47 浏览: 38
以下是Python中判断超大素数的实现方法:
```python
import random
# Miller-Rabin素性检验算法
def Miller_Rabin(n, k):
if n == 2 or n == 3:
return True
if n == 1 or n % 2 == 0:
return False
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for i in range(k):
a = random.randint(2, n - 2)
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for j in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
# 判断是否为超大素数
def is_prime(n):
if n < 2:
return False
# 小于1000的素数表
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
if n in primes:
return True
for p in primes:
if n % p == 0:
return False
# Miller-Rabin素性检验算法
return Miller_Rabin(n, 10)
# 测试
n = int(input("请输入一个数:"))
if is_prime(n):
print(n, "是超大素数")
else:
print(n, "不是超大素数")
```
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)