python脚本判断一个数是否为素数的几种方法
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。素数在数论中有着很重要的地位。比1大但不是素数的数称为合数。1和0既非素数也非合数。质数是与合数相对立的两个概念，二者构成了数论当中最基础的定义之一。基于质数定义的基础之上而建立的问题有很多世界级的难题，如哥德巴赫猜想等。算术基本定理证明每个大于1的正整数都可以写成素数的乘积，并且这种乘积的形式是唯一的。这个定理的重要一点是，将1排斥在素数集合以外。如果1被认为是素数，那么这些严格的阐述就不得不加上一些限制条件。
前几天偶尔的有朋友问python怎么判断素数的方法，走网上查了查，总结了python脚本判断一个数是否为素数的几种方法：
#运用python的数学函数 &
import math &
def isPrime(n): &
& & if n &= 1: &
& & return False&
& & for i in range(2, int(math.sqrt(n)) + 1): &
& & if n % i == 0: &
& & & & return False&
& & return True&
#单行程序扫描素数 &
from math import sqrt &
[ p for p in & range(2, N) if 0 not in [ p% d for d in range(2, int(sqrt(p))+1)] ] &
#运用python的itertools模块 &
from itertools import count &
def isPrime(n): &www.2cto.com
& & if n &= 1: &
& & & & return False&
& & for i in count(2): &
& & & & if i * i & n: &
& & & & & & return True&
& & & & if n % i == 0: &
& & & & & & return False&
#不使用模块的两种方法 &
def isPrime(n): &
& & if n &= 1: &
& & & & return False&
& & i = 2&
& & while i*i &= n: &
& & & & if n % i == 0: &
& & & & & & return False&
& & & & i += 1&
& & return True&
def isPrime(n): &
& & if n &= 1: &
& & & & return False&
& & if n == 2: &
& & & & return True&
& & if n % 2 == 0: &
& & & & return False&
& & i = 3&
& & while i * i &= n: &
& & & & if n % i == 0: &
& & & & & & return False&
& & & & i += 2&
& & return True&&nbsp>&nbsp
&nbsp>&nbsp
&nbsp>&nbsp
python脚本判断一个数是否为素数的几种方法
摘要：质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。素数在数论中有着很重要的地位。比1大但不是素数的数称为合数。1和0既非素数也非合数。质数是与合数相对立的两个概念,二者构成了数论当中最基础的定义之一。基于质数定义的基础之上而建立的问题有很多世界级的难题,如哥德巴赫猜想等。算术基本定理证明每个大于1的正整数都可以写成素数的乘积,并且这种乘积的形式是唯一的。这个定理的重要一点是,将1排斥在素数集合以外。如果1被认为是素数,那么这些严格的阐述就
质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。素数在数论中有着很重要的地位。比1大但不是素数的数称为合数。1和0既非素数也非合数。质数是与合数相对立的两个概念,二者构成了数论当中最基础的定义之一。基于质数定义的基础之上而建立的问题有很多世界级的难题,如哥德巴赫猜想等。算术基本定理证明每个大于1的正整数都可以写成素数的乘积,并且这种乘积的形式是唯一的。这个定理的重要一点是,将1排斥在素数集合以外。如果1被认为是素数,那么这些严格的阐述就不得不加上一些限制条件。
前几天偶尔的有朋友问python怎么判断素数的方法,走网上查了查,总结了python脚本判断一个数是否为素数的几种方法:
#运用python的数学函数 &
import math &
def isPrime(n): &
& & if n &= 1: &
& & return False&
& & for i in range(2, int(math.sqrt(n)) + 1): &
& & if n % i == 0: &
& & & & return False&
& & return True&
#单行程序扫描素数 &
from math import sqrt &
[ p for p in & range(2, N) if 0 not in [ p% d for d in range(2, int(sqrt(p))+1)] ] &
#运用python的itertools模块 &
from itertools import count &
def isPrime(n): &www.2cto.com
& & if n &= 1: &
& & & & return False&
& & for i in count(2): &
& & & & if i * i & n: &
& & & & & & return True&
& & & & if n % i == 0: &
& & & & & & return False&
#不使用模块的两种方法 &
def isPrime(n): &
& & if n &= 1: &
& & & & return False&
& & i = 2&
& & while i*i &= n: &
& & & & if n % i == 0: &
& & & & & & return False&
& & & & i += 1&
& & return True&
def isPrime(n): &
& & if n &= 1: &
& & & & return False&
& & if n == 2: &
& & & & return True&
& & if n % 2 == 0: &
& & & & return False&
& & i = 3&
& & while i * i &= n: &
& & & & if n % i == 0: &
& & & & & & return False&
& & & & i += 2&
& & return True&
以上是的内容，更多
的内容，请您使用右上方搜索功能获取相关信息。
若你要投稿、删除文章请联系邮箱：zixun-group@service.aliyun.com,工作人员会在五个工作日内给你回复。
云服务器 ECS
可弹性伸缩、安全稳定、简单易用
&40.8元/月起
预测未发生的攻击
&24元/月起
为您提供0门槛上云实践机会
你可能还喜欢
你可能感兴趣
阿里云教程中心为您免费提供
python脚本判断一个数是否为素数的几种方法相关信息，包括
的信息，所有python脚本判断一个数是否为素数的几种方法相关内容均不代表阿里云的意见！投稿删除文章请联系邮箱：zixun-group@service.aliyun.com，工作人员会在五个工作日内答复
售前咨询热线
服务与支持
账号与支持
关注阿里云
International如何判断一个数是不是素数(prime&number)&方法
费马小定理：对于两个互质的素数N和P，必有：N^(P-1)%P=1
那么我们通过这个性质来判断素数吧，当然，你会担心当P很大的时候乘方会很麻烦。不用担心！我们上面不是有个快速的幂模算法么？好好的利用蒙格马利这位大数学家为我们带来的快乐吧！
算法思路是这样的：
对于N，从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，N仍未测试失败，那么则认为N是素数。当然，测试次数越多越准确，但一般来讲50次就足够了。另外，预先用“小学生”的算法构造一个包括500个素数的数组，先对Q进行整除测试，将会大大提高通过率，方法如下：
bool IsPrime3(unsigned n)
&&& if ( n
小于2的数即不是合数也不是素数
&&& static
unsigned aPrimeList[] = {
2, 3, 5, 7, 11, 17, 19, 23, 29, 31, 41,
43, 47, 53, 59, 67, 71, 73, 79, 83, 89, 97
&&& const int
nListNum = sizeof(aPrimeList) / sizeof(unsigned);
&&& for (int
i=0;i&nListN++i)
按照素数表中的数对当前素数进行判断
if (1!=Montgomery(aPrimeList[i],n-1,n)) // 蒙格马利算法
&&&&&&&&&&&
&&& return
OK，这就专家的作法了。
等等，什么？好像有点怪，看一下这个数29341，它等于13 * 37 *
61，显然是一个合数，但是竟通过了测试！！哦，抱歉，我忘了在素数表中加入13，37，61这三个数，我其实是故意的，我只是想说明并费马测试并不完全可靠。
现在我们发现了重要的一点，费马定理是素数的必要条件而非充分条件。这种不是素数，但又能通过费马测试的数字还有不少，数学上把它们称为卡尔麦克数，现在数学家们已经找到所有10
16以内的卡尔麦克数，最大的一个是3329。我们必须寻找更为有效的测试方法。数学家们通过对费马小定理的研究，并加以扩展，总结出了多种快速有效的素数测试方法，目前最快的算法是拉宾米勒测试算法，下面介绍拉宾米勒测试。
本文来自CSDN博客，转载请标明出处：file:///C:/Documents and Settings/Liao
Chengxuan/桌面/如何判断一个数是否为素数 - leohxj的专栏 - CSDN博客.mht
拉宾米勒测试
拉宾米勒测试是一个不确定的算法，只能从概率意义上判定一个数可能是素数，但并不能确保。算法流程如下:
1.选择T个随机数A，并且有A&N成立。
2.找到R和M，使得N=2*R*M+1成立。
快速得到R和M的方式：N用二进制数B来表示，令C=B-1。因为N为奇数（素数都是奇数），所以C的最低位为0，从C的最低位的0开始向高位统计，一直到遇到第一个1。这时0的个数即为R，M为B右移R位的值。
3.如果A^M%N=1，则通过A对于N的测试，然后进行下一个A的测试
4.如果A^M%N!=1，那么令i由0迭代至R，进行下面的测试
5.如果A^((2^i)*M)%N=N-1则通过A对于N的测试，否则进行下一个i的测试
6.如果i=r，且尚未通过测试，则此A对于N的测试失败，说明N为合数。
7.进行下一个A对N的测试，直到测试完指定个数的A
通过验证得知，当T为素数，并且A是平均分布的随机数，那么测试有效率为1 / ( 4 ^ T )。如果T
8那么测试失误的机率就会小于10^(-5)，这对于一般的应用是足够了。如果需要求的素数极大，或着要求更高的保障度，可以适当调高T的值。下面是代码：
bool RabbinMillerTest( unsigned n )
小于2的数即不是合数也不是素数
nPrimeListSize=sizeof(g_aPrimeList)/sizeof(unsigned);//求素数表元素个数
&&& for(int
i=0;i&nPrimeListS++i)
按照素数表中的数对当前素数进行判断
if (n/2+1&=g_aPrimeList[i])
{// 如果已经小于当前素数表的数，则一定是素数
&&&&&&&&&&&
if (0==n%g_aPrimeList[i])
{// 余数为0则说明一定不是素数
&&&&&&&&&&&
&&& // 找到r和m，使得n
= 2^r * m + 1;
&&& int r = 0, m
= n - 1; // ( n - 1 ) 一定是合数
&&& while ( 0 ==
( m & 1 ) )
m &&= 1; // 右移一位
r++; // 统计右移的次数
unsigned nTestCnt = 8; // 表示进行测试的次数
unsigned i = 0; i & nTestC ++i )
利用随机数进行测试，
int a = g_aPrimeList[ rand() % nPrimeListSize ];
if ( 1 != Montgomery( a, m, n ) )
&&&&&&&&&&&
int j = 0;
&&&&&&&&&&&
int e = 1;
&&&&&&&&&&&
for ( ; j & ++j )
&&&&&&&&&&&
&&&&&&&&&&&&&&&
if ( n - 1 == Montgomery( a, m * e, n ) )
&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&
&&&&&&&&&&&
&&&&&&&&&&&
if (j == r)
&&&&&&&&&&&
&&&&&&&&&&&&&&&
&&&&&&&&&&&
&&& return
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)