利用费马小定理判断一个数是否为质数

admin 提交于 周四, 10/10/2019 - 10:52

Python程序如下:

"""221 may be a prime number."""

import random

def isprime(n,k=128):

if n<2:

return False

for _ in range(k):

a = random.randrange(1,n)

if pow(a,n-1,n)!=1:

return False

return True

参考:https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86 

Miller-Rabin算法可以把准确度提高4倍,参考:https://blog.csdn.net/s031302306/article/details/51606018

 

标签

添加新评论

Restricted HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id> <img src>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。
验证码
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
请输入"汉语"