查看: 7723|回复: 24
如何判断质数、合数？谢谢
阅读权限20
在线时间 小时
(1.43 KB, 下载次数: 83)
15:34 上传
点击文件名下载附件
如何判断质数、合数？谢谢
阅读权限70
在线时间 小时
& & & & & & & &
B1=IF(ISNUMBER(MATCH(A1,{1,2,3,5,7},0)),"质数","合数")下拉
[此贴子已经被作者于 17:08:41编辑过]
阅读权限20
在线时间 小时
阅读权限150
在线时间 小时
以下是引用zhxbsc在 15:48:24的发言：B1=IF(ISNUMBER(MATCH(A1,{1,2,3,5,7,9},0)),"质数","合数")下拉1 非质非合。9是合数。
阅读权限150
在线时间 小时
=IF(A1&2,"",IF((A1&&2)*OR(MOD(A1,ROW(INDIRECT("2:"&A1-1)))=0),"合","质"))
阅读权限70
在线时间 小时
以下是引用chrisfang在 17:07:14的发言：1 非质非合。9是合数。谢谢提醒，我只是针对问题做的，对于9的是笔误，多写一个再次感谢提醒！！
阅读权限150
在线时间 小时
以下是引用zhxbsc在 17:09:47的发言：谢谢提醒，我只是针对问题做的，对于9的是笔误，多写一个再次感谢提醒！！呵呵，不好意思我没看问题，只看了标题。
阅读权限70
在线时间 小时
我得谢谢你，不然把这个质数的概念都弄错了1 非质非合，这是公理。
阅读权限95
在线时间 小时
陈军版主的质数公式：=IF(AND(A1&4,A1=INT(A1)),IF(OR(INT(A1/ROW(INDIRECT("2:"&INT(SQRT(A1)))))*ROW(INDIRECT("2:"&INT(SQRT(A1))))=A1),"非质数","质数"),IF(OR(A1={2,3}),"质数","非质数"))链接：& 的第一个压缩包中的第三张表中。
阅读权限95
在线时间 小时
以下是引用hbhfgh4310在 19:48:15的发言：陈军版主的质数公式：=IF(AND(A1&4,A1=INT(A1)),IF(OR(INT(A1/ROW(INDIRECT("2:"&INT(SQRT(A1)))))*ROW(INDIRECT("2:"&INT(SQRT(A1))))=A1),"非质数","质数"),IF(OR(A1={2,3}),"质数","非质数"))链接：& 的第一个压缩包中的第三张表中。还可以简化：=IF(A1=1,"非质非合",IF(OR(A1&4,PRODUCT(MOD(A1,ROW(INDIRECT("2:"& INT(A1^0.5)))))),"质数","合数"))
最新热点 /1
ExcelHome每周都有线上直播公开课，
国内一流讲师真身分享，高手贴身答疑，
赶不上直播还能看录像，
关键居然是免费的！
厚木哥们都已经这么努力了，
你还好意思说学不好Office。
玩命加载中，请稍候
玩命加载中，请稍候
Powered by
本论坛言论纯属发表者个人意见，任何违反国家相关法律的言论，本站将协助国家相关部门追究发言者责任！ & & 本站特聘法律顾问：徐怀玉律师 李志群律师57864人阅读
Algorithm & Data Structure（6）
x%y为x取模y，即x除以y所得的余数，当x&y时，x%y=x，所有取模的运算对象都为整数。
x^y表示x的y次方。乘方运算的优先级高于乘除和取模，加减的优先级最低。
见到x^y/z这样，就先算乘方，再算除法。
A/B，称为A除以B，也称为B除A。
若A%B=0，即称为A可以被B整除，也称B可以整除A。
A*B表示A乘以B或称A乘B，B乘A，B乘以A……都一样。
复习一下小学数学
公因数：两个不同的自然数A和B，若有自然数C可以整除A也可以整除B，那么C就是A和B的公因数。
公倍数：两个不同的自然数A和B，若有自然数C可以被A整除也可以被B整除，那么C就是A和B的公倍数。
互质数：两个不同的自然数，它们只有一个公因数1，则称它们互质。
费马是法国数学家，又译“费尔马”，此人巨牛，他的简介请看下面。不看不知道，一看吓一跳。
费马人物简介：　　
2.费马小定理：
有N为任意正整数，P为素数，且N不能被P整除（显然N和P互质），则有：N^P%P=N(即：N的P次方除以P的余数是N)。
但是我查了很多资料见到的公式都是这个样子：
(N^(P-1))%P=1后来分析了一下，两个式子其实是一样的，可以互相变形得到。
原式可化为：(N^P-N)%P=0(即：N的P次方减N可以被P整除，因为由费马小定理知道N的P次方除以P的余数是N)把N提出来一个，N^P就成了你N*(N^(P-1))，那么(N^P-N)%P=0可化为：
(N*(N^(P-1)-1))%P=0
请注意上式，含义是：N*(N^(P-1)-1)可以被P整除
又因为N*(N^(P-1)-1)必能整除N（这不费话么!）
所以，N*(N^(P-1)-1)是N和P的公倍数，小学知识了^_^
又因为前提是N与P互质，而互质数的最小公倍数为它们的乘积，所以一定存在
正整数M使得等式成立：N*(N^(P-1)-1)=M*N*P
两边约去N，化简之：N^(P-1)-1=M*P
因为M是整数，显然：N^(P-1)-1)%P=0即：N^(P-1)%P=1
============================================
3.积模分解公式
先有一个引理，如果有：X%Z=0，即X能被Z整除，则有：(X+Y)%Z=Y%Z
设有X、Y和Z三个正整数，则必有：(X*Y)%Z=((X%Z)*(Y%Z))%Z
想了很长时间才证出来，要分情况讨论才行：
1.当X和Y都比Z大时，必有整数A和B使下面的等式成立：
X=Z*I+A（1）
Y=Z*J+B（2）
不用多说了吧，这是除模运算的性质！
将（1）和（2）代入(X*Y)modZ得：((Z*I+A)(Z*J+B))%Z乘开，再把前三项的Z提一个出来，变形为：(Z*(Z*I*J+I*A+I*B)+A*B)%Z（3）
因为Z*(Z*I*J+I*A+I*B)是Z的整数倍……晕，又来了。
概据引理，（3）式可化简为：(A*B)%Z又因为：A=X%Z，B=Y%Z，代入上面的式子，就成了原式了。
2.当X比Z大而Y比Z小时，一样的转化：
X=Z*I+A
代入(X*Y)%Z得：
(Z*I*Y+A*Y)%Z
根据引理，转化得：(A*Y)%Z
因为A=X%Z，又因为Y=Y%Z，代入上式，即得到原式。
同理，当X比Z小而Y比Z大时，原式也成立。
3.当X比Z小，且Y也比Z小时，X=X%Z，Y=Y%Z，所以原式成立。
=====================================================
4.快速计算乘方的算法
如计算2^13，则传统做法需要进行12次乘法。
/*计算n^p*/
unsigned power(unsigned n,unsigned p)
for(int i=0;i&p;i++) n*=n;
该死的乘法，是时候优化一下了！把2*2的结果保存起来看看，是不是成了：
4*4*4*4*4*4*2
再把4*4的结果保存起来：16*16*16*2
一共5次运算，分别是2*2、4*4和16*16*16*2
这样分析，我们算法因该是只需要计算一半都不到的乘法了。
为了讲清这个算法，再举一个例子2^7：2*2*2*2*2*2*2
两两分开：(2*2)*(2*2)*(2*2)*2
如果用2*2来计算，那么指数就可以除以2了，不过剩了一个，稍后再单独乘上它。
再次两两分开，指数除以2： ((2*2)*(2*2))*(2*2)*2
实际上最后一个括号里的2 * 2是这回又剩下的，那么，稍后再单独乘上它 现在指数已经为1了，可以计算最终结果了：16*4*2=128
优化后的算法如下：
unsigned Power(unsigned n,unsigned p)
unsigned main=n; //用main保存结果
unsigned odd=1; //odd用来计算“剩下的”乘积
while (p&1)
{//一直计算，直到指数小于或等于1
if((p%2)!=0)
{// 如果指数p是奇数，则说明计算后会剩一个多余的数，那么在这里把它
乘到结果中
odd*= //把“剩下的”乘起来
main*= //主体乘方
p/=2; //指数除以2
return main* //最后把主体和“剩下的”乘起来作为结果
够完美了吗？不，还不够！看出来了吗？main是没有必要的，并且我们可以有更快的代码来判断奇数。要知道除法或取模运算的效率很低，所以我们可以利用偶数的一个性质来优化代码，那就是偶数的二进制表示法中的最低位一定为0!
unsigned Power(unsigned n, unsigned p)
{ // 计算n的p次方
unsigned odd = 1; //oddk用来计算“剩下的”乘积
while (p & 1)
{ // 一直计算到指数小于或等于1
if (( p & 1 )!=0)
{ // 判断p是否奇数，偶数的最低位必为0
odd *= // 若odd为奇数，则把“剩下的”乘起来
n *= // 主体乘方
p /= 2; // 指数除以2
return n * // 最后把主体和“剩下的”乘起来作为结果
========================================================
5.&蒙格马利”快速幂模算法
后面我们会用到这样一种运算：(X^Y)%Z。但问题是当X和Y很大时，只有32位的整型变量如何能够有效的计算出结果？
考虑上面那份最终的优化代码和再上面提到过的积模分解公式，我想你也许会猛拍一下脑门，吸口气说：“哦，我懂了！”。
下面的讲解是给尚没有做出这样动作的同学们准备的：
X^Y可以看作Y个X相乘，即然有积模分解公式，那么我们就可以把Y个X相乘再取模的过程分解开来，比如：(17^25)%29则可分解为：(
( 17 * 17 ) % 29 * ( 17 * 17 ) % 29 * ……
如果用上面的代码将这个过程优化，那么我们就得到了著名的“蒙格马利”快速幂模算法：
unsigned Montgomery(unsigned n, unsigned p, unsigned m)
{ // 快速计算 (n ^ e) % m 的值，与power算法极类似
unsigned r = n % // 这里的r可不能省
unsigned k = 1;
while (p & 1)
if ((p & 1)!=0)
k = (k * r) % // 直接取模
r = (r * r) % // 同上
return (r * k) % // 还是同上
上面的代码还可以优化。下面是蒙格马利极速版：
unsigned Montgomery(unsigned n,unsigned p,unsigned m)
{ //快速计算(n^p)%m的值
unsignedk=1;
while(p!=1)
if(0!=(p&1))k=(k*n)%m;
n=(n*n)%m;
return(n*k)%m;
=====================================================
6.怎么判断一个数是否为素数？
1)笨蛋的作法：
bool IsPrime(unsigned n)
//小于2的数即不是合数也不是素数
for (unsigned i=2;i&n;++i)
//和比它小的所有的数相除，如果都除不尽，证明素数
if (n%i==0)
//除尽了，则是合数
}一个数去除以比它的一半还要大的数，一定除不尽，所以还用判断吗？？
2)下面是小学生的做法：
bool IsPrime(unsigned n)
//小于2的数即不是合数也不是素数
for(unsigned i=2;i&n/2+1;++i)
// 和比它的一半小数相除，如果都除不尽，证明素数
if ( 0 == n % i )
// 除尽了，合数
// 都没除尽，素数
一个合数必然可以由两个或多个质数相乘而得到。那么如果一个数不能被比它的一半小的所有的质数整除，那么比它一半小的所有的合数也一样不可能整除它。建立一个素数表是很有用的。
3)下面是中学生的做法：
bool IsPrime2(unsigned n)
if ( n & 2 )
{ // 小于2的数即不是合数也不是素数
static unsigned aPrimeList[] = { // 素数表
1, 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, 113,
193, 241, 257, 337, 353, 401, 433, 449, 577, 593, 641,
673, 769, 881, 929, 977, , , 1249,
, , , , 1873,
, , , , 2593,
, , , , 3089,
, , , , 3617,
, , , , 4241,
, , , , 4721,
, , , , 5393,
, , , , 6353,
, , , , 6961,
, , , , 7649,
, , , , 8209,
, , , , 8753,
, , , , 9601,
const int nListNum = sizeof(aPrimeList)/sizeof(unsigned);//计算素数表里元素的个数
for (unsigned i=2;i&nListN++i )
if(n/2+1&aPrimeList[i])
if(0==n%aPrimeList[i])
/*由于素数表中元素个数是有限的，那么对于用素数表判断不到的数，就只有用笨蛋办法了*/
for (unsigned i=aPrimeList[nListNum-1];i&n/2+1;i++ )
if (0==n%i)
// 除尽了，合数
}& & & & 还是太糟了，我们现在要做的对于大型素数的判断，那个素数表倒顶个P用！当然，我们可以利用动态的素数表来进行优化，这就是大学生的做法了。但是动态生成素数表的策略又复杂又没有效率，所以我们还是直接跳跃到专家的做法吧：
& & & & 根据上面讲到的费马小定理，对于两个互质的素数N和P，必有：N^(P-1)%P=1 ,那么我们通过这个性质来判断素数吧，当然，你会担心当P很大的时候乘方会很麻烦。不用担心！我们上面不是有个快速的幂模算法么？好好的利用蒙格马利这位大数学家为我们带来的快乐吧！
算法思路是这样的：
& & & & 对于N，从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，N仍未测试失败，那么则认为N是素数。当然，测试次数越多越准确，但一般来讲50次就足够了。另外，预先用“小学生”的算法构造一个包括500个素数的数组，先对Q进行整除测试，将会大大提高通过率，方法如下:
6)下面是专家的做法：
bool IsPrime3(unsigned n)
if ( n & 2 )
// 小于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)) // 蒙格马利算法
}& & & & OK，这就专家的作法了。
& & & & 等等，什么？好像有点怪，看一下这个数29341，它等于13 * 37 * 61，显然是一个合数，但是竟通过了测试！！哦，抱歉，我忘了在素数表中加入13，37，61这三个数，我其实是故意的，我只是想说明并费马测试并不完全可靠。
& & & & 现在我们发现了重要的一点，费马定理是素数的必要条件而非充分条件。这种不是素数，但又能通过费马测试的数字还有不少，数学上把它们称为卡尔麦克数，现在数学家们已经找到所有10
^ 16以内的卡尔麦克数，最大的一个是3329。我们必须寻找更为有效的测试方法。数学家们通过对费马小定理的研究，并加以扩展，总结出了多种快速有效的素数测试方法，目前最快的算法是拉宾米勒测试算法，下面介绍拉宾米勒测试。
================================================================
7.拉宾米勒测试
& & & & 拉宾米勒测试是一个不确定的算法，只能从概率意义上判定一个数可能是素数，但并不能确保。算法流程如下:
& & & &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的数即不是合数也不是素数
const unsigned 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++; // 统计右移的次数
const unsigned nTestCnt = 8; // 表示进行测试的次数
for ( 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)
以上内容载自博客园并稍加编辑：
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：101138次
排名：千里之外
原创：28篇
评论：47条
(2)(4)(8)(15)扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
如何快速判断一个较大的数是质数还是合数？如何快速判断一个较大的数是质数还是合数，例如359999
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
359999不是质数。 找到一个接近于这个数的完全平方数，然后在0到那个完全平方数内的所有整数一一试除，除1以外能除得下的，则为合数。由于历代数学家没有找到一个公式可以判断一个数是否为质数，所以只能用试除的方式去检验。
比如350，350=200＋150=10×20＋15×10=2×5×2×2×5＋3×5×2×5=2×5×5×（2×2＋3），所以它不是质数！！！
质数只有1和它本身这两个因数的自然数叫做质数。还可以说成质数只有1和它本身何其它两个整数的乘积。例如，15＝3×5，所以15不是素数
通常按以下步骤：1、不是偶数（2除外）；2、不是5的倍数（末位数字不是0或5）；3、不是3的倍数（各个数字之和不是3的倍数）；……
为您推荐：
扫描下载二维码我要文库申报
查看: 2480|回复: 3
疑难76 如何判断自然数是质数还是合数
积分学习力
魅力值 影响力
消费券 Ti币好友
在线时间 小时
最后登录月度优秀 次管理次数 次
网站名称: Excel技巧网 | Excel专家栖息谷 | 微软中文技术社区合作伙伴
署名作者: lrlxxqxa
版权声明: 版权归本站与作者共有 除本站官方外非作者本人转载须经许可并注明出处
适用版本: 2010&
语言环境: 简体中文
学习方法: 掌握Excel技巧的关键是动手操作
下载 ≠ 知识
免费注册成为本站会员，享用更多功能，结识更多Office办公高手！
才可以下载或查看，没有帐号？
本帖最后由 lrlxxqxa 于
16:01 编辑
学office，哪能不关注全网最大的Office类微博（新浪）
初级三, 积分 283, 距离下一级还需 217 积分
积分学习力
魅力值 影响力
消费券 Ti币好友
在线时间 小时
最后登录月度优秀 次
这个可以有,呵呵
学office，哪能不关注全网最大的Office类微博（新浪）
积分学习力
魅力值 影响力
消费券 Ti币好友
在线时间 小时
最后登录月度优秀 次管理次数 次
学office，哪能不关注全网最大的Office类微博（新浪）
高级一, 积分 1710, 距离下一级还需 190 积分
积分学习力
魅力值 影响力
消费券 Ti币好友
在线时间 小时
最后登录月度优秀 次
版主博学多才啊
学office，哪能不关注全网最大的Office类微博（新浪）
Excel技巧网的会员探讨问题仅代表其个人意见，与网站的立场无关。任何违反国家和地方相关法律法规的言论，本站有义务协助政府相关部门追究发言者的责任！
本站中非注明转载文章与案例的版权为作者与Excel技巧网共有。若非原文作者，本站之外任何单位或个人未经允许，不得将其用于商业用途。
若非原文作者，任何形式的非商业性转载必须获得Excel技巧网或作者允许，并注明作者和出处。
会员发表的帖子如涉及版权纠纷，须自行负责。详情请参考注册时的网站服务条款。
本站特聘法律顾问：沈学律师
Powered by查看: 3779|回复: 8
如何判断质数与合数
本帖最后由 epsonstar 于
23:18 编辑
(1.59 KB, 下载次数: 57)
22:39 上传
点击文件名下载附件
其中,1,2均为质数
1不是质数！别搞错了！&
这个好像是函中班的练习题。
=if(a1=2,&质数&,if(mod(a1,2),&合数&,&质数&))
二楼明显有问题......................................................
epsonstar 发表于
二楼明显有问题......................................................
能告诉下什么是质数、什么是合数吗？
本帖最后由 周义坤 于
20:40 编辑
laoda1228 发表于
能告诉下什么是质数、什么是合数吗？
数组公式：=IF(SUM(N(MOD(A1,ROW(INDIRECT(&1:&&A1)))=0))=2,&质数&,&合数&)复制代码如果1要为的话，公式改改就可以了：=IF(SUM(N(MOD(A1,ROW(INDIRECT(&1:&&A1)))=0))&3,&质数&,&合数&复制代码
1既不算质数也不算合数的吧
蝶·舞 发表于
1既不算质数也不算合数的吧
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
1不是质数也是合数
5楼正解，也来学习一哈
B2=IF(SUMPRODUCT((MOD(A2,ROW($1:$20))=0)*1)=2,&质数&,&&)
C2=IF(SUMPRODUCT((MOD(A2,ROW($1:$20))=0)*1)=2,&&,&合数&)
下拉复制代码
Powered by}