首页 / 算法 / 素数判断算法(基于python实现)
素数判断算法(基于python实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了素数判断算法(基于python实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1688字,纯文字阅读大概需要3分钟。
内容图文
素数是只能被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
内容总结
以上是互联网集市为您收集整理的素数判断算法(基于python实现)全部内容,希望文章能够帮你解决素数判断算法(基于python实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。