判定一个较大数是否是质数

“N法”判断一个较大数是质数与合数的方法

首先让我们来认识一下质数与合数的概念。

质数：只有1和它本身两个因数的自然数。

合数：除了1和它本身还有其它因数的自然数。

对于判断一个较大数是质数与合数，学生往往难于下手，怎样克服这样的难点呢？请看这道例题的解题过程。

例题：判断713是质数还是合数？

解题过程：

第一步：713＜729=272

第二步：

1、列出小于27的所有质数：

2、

3、5、7、11、13、17、19、23

2、用2、

3、5、7、11、13、17、19、23依次去除713。得出713÷ 23=31

第三步：判断：有质数23能整除713，则713是合数。

以上这种解题方法通常称为“N法”。

下面我们来总结一下，如果用“N法”来判别呢？主要分为三个步骤：

第一步：找出大于N且最接近N的平方数K2。

第二步：用小于K的所有质数去除N

第三步：判断。如果这些质数都不能整除N，那么N是质数；如果这些质数中至少有一个能整除N，那么N就是合数。

下面请大家来尝试一下如何用“N法”来判断一个较大的数是质数还是合数。

练习：判断277、437、97、89、53是质数还是合数？

如何判断一个数能否被2至19的质数整除的简单方法

(2)若一个整数的末位是偶数，如0、2、4、6或8，则这个数能被2整除。 (3)若一个整数的所有位上的数字之和能被3整除，则这个整数能被3整除。 (4) 若一个整数的末尾两位数能被4整除，则这个数能被4整除。 (5)若一个整数的末位是0或5，则这个数能被5整除。 (6)若一个整数能被2和3整除，则这个数能被6整除。 倍数，则原数能被7整除。如6139，613－9×2＝595 ， 59－5×2＝49，所以6139是7的 倍数。如105，0 (9)若一个整数的所有位上的数字之和能被9整除，则这个整数能被9整除。 （11）若一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除。 11去掉个位数，再从余下的数中，减去个位数，如果差是11的倍数，则原数能被11整除。例如，判断10901是否11的倍数的过程如下：1090－1＝1089 ，108－9＝99，所以10901是11的倍数。 （13）原因：相当于1000除以13余-1，那么1000^2除以13余1（即-1的平方）,1000^3除以13余-1,……所以 13整除。如1963，196+3×4=208，20+8×4=52，所以能被13 整除。如104，26 方法二：对一个位数很多的数（比如：51 578 953 270），从右向左每3位隔开，从右向左依次加、减，270-953+578-51=-156能被13整除，则原数能被13整除。 （17 17整除。 注意：如果数字仍然太大不能直接观察出来，就重复此过程。 例如：判断1675282能不能被17整除。167528-2×5=167518 16751-8×5=16711 1671-1×5=1666 166-6×5=136 到这里如果你仍然观察不出来，就继续…… 6×5=30，现在个位×5=30>剩下的13，就用大数减去小数，30-13=17，所以1675282能被 17整除。如102，0 （19 19整除。 如果数字仍然太大不能直接观察出来，就重复此过程。 如：32148，3214+18=3230，32+3×2＝38；如114，19

求素数列表和判断素数的算法

求素数列表和判断素数的算法 有兴趣阅读本文的读者，应该对素数概念是十分熟悉的了。用计算机程序实现素数计算，集中在2个主要问题上： ?判断一个正整数是否是素数-（算法A） ?求一定范围内的素数列表- （算法B） 关于素数的算法，根据素数的数学性质，大家都会想到如下几个方面： ?用遍历求模的方式判断素数 ?素数都是奇数，可以在奇数数列中寻找素数 ?利用开方来缩小搜索的范围 然后，求素数的计算是复杂的，如果算法写得不好，则耗时较高。在百度百科“素数”条目中的算法程序，是值得商榷的。很多方法是O(N2)的算法。 为此，在本文中探讨了求素数列表和判断素数这两个算法，力图使算法可以达到O （N Log(N)）优化级别。在本文中，算法语言选用C#。 1,判断素数的简单实现（算法A-1） ///

///算法A-1，判断素数 ///

///待测正整数 ///是否为素数（为了简化，1以下的整数皆为素数） public static bool IsPrime(int number) { // 为了简化，1以下的整数皆为素数 if(number <= 2) { return true; } // 奇偶性 if (number % 2 == 0) { return false; } // 利用开方缩小范围，优化效果十分明显 int range = (int)Math.Sqrt(number) + 1; // 从3开始的奇数列 for (int current = 3; current <= range; current += 2) { // 判断是否为素数 if (number % current == 0)

判断某个数是否素数

判断某个数是否素数： 1.定义为一个function函数过程 第一种方法： Function prime(ByVal x As Integer) As Boolean 注1 For i = 2 To x – 1 注2 If x Mod i = 0 Then Exit For Next i If i > x - 1 Then prime = True 注3 End Function 注1：这里注意形参前面有ByVal，不要ByVal也是可以的，为什么？ 因为在function中并未改变x的值，所以加不加ByVal都正确 注2：此句也可以这样写：For i = 2 To x/2 或 For i = 2 To sqr(x) 注3：此句也可以这样写：If i > x - 1 Then prime = True Else prime = False 思考：为什么不要Else prime = False 程序运行也是正确的 另外注意此处的条件i > x – 1的实际含义 调用的时候（调用函数时，最好不要用带call关键字的调用方法） If prime(x) then……… 第二种方法： Function prime(ByVal x As Integer) As Boolean Prime=false 注1 For i = 2 To x – 1 If x Mod i = 0 Then Exit Function注2 Next i prime = True 注3 End Function 注1 此句要不要都可以，思考为什么 注2和注3两条语句与第一种方法的区别 调用的时候 If prime(x) then……… 第三种方法： Function prime(ByVal x As Integer) As integer Prime=0 For i = 2 To x – 1 If x Mod i = 0 Then Exit Function Next i prime = 1 End Function 此方法与上述方法的区别 调用的时候 If prime(x)=1 then………

质数的判定

质数的判定 舒云水 课本第3页的例1及例1后面的探究问题是“质数的判定” 问题，它有丰富的数学背景，下面给读者做一个简单介绍﹒质数有无穷多个﹒大约在2300年前欧几里得就证明了存在着无穷多个质数﹒尽管如此，迄今为止还没有发现质数的模型或产生质数的有效公式﹒因而寻找大的质数必须借助计算机一个一个地找﹒寻找大质数是数论研究的重要课题之一﹒目前找到的最大质数是梅森质数1 243112609 ，它有12978189位数，如果用普通字号将这个巨数连续写下来，它的长度可超过50公里！ 读者可能会产生一个疑问：找大质数有什么用？现在最好的密码是用质数制造的，极难破译﹒ 人们一直在寻找检验一个数是否为质数的方法，最近一些年有了巨大进步﹒你或许会说，检验质数有什么难？确实，看一个数是不是质数，有一种非常自然而直接的方法，这就是我们常用的试除法，即课本例1所用的算法﹒这一方法对检验不太大的数是挺实用的﹒但若数字太大，它就变得十分笨拙﹒假设你在一个快速计算机上实用高效的程序进行试除﹒对于一个10位数字的数，运行程序几乎瞬间就能完成﹒对于一个20位的数就麻烦一点了，需要两个小时﹒对于一个50位的数，则需要100亿年﹒这已经大得不可想象﹒前面讲过最好的密码是用质数制造的，它是用介于60位到100位之间的两个质数制造的，这种计算正是制造这种密码的需要﹒当今庞大的国际数

据通讯网络能安全运行，就得益于这种密码﹒ 如何确定一个100位的数是否为质数呢？数学家做了许多努力，在1980年左右找到了目前可用的最好方法﹒数学家阿德勒曼，鲁梅利，科恩和伦斯特拉研究出一种非常复杂的方法﹒现在以他们的名字的第一个字母命名为ARCL检验法﹒在上面提到的那类计算机上进行ARCL检验，对20位的数只需10秒钟，对50位的数用15秒，100位的数用40秒﹒如果要检查1000位的数，一个星期也就够了﹒可以相信，随着人们对质数的判定算法的研究不断深入及计算机技术的迅猛发展，我们会找到更好更快地检验一个大数是否为质数的方法，发现更多更大的质数﹒

C语言素数的几种判断方法

#include #include main() { int i,n; printf("请输入一个数："); scanf("%d",&n); for(i=2;i=n) printf("素数！"); printf("\n"); } /*main() { int i,n,m; printf("请输入一个整数："); scanf("%d",&m); n=(int)sqrt(m); for(i=2;i<=n;i++) if(m%i==0) break; if(i>n) printf("素数！\n"); else printf("不是素数！"); }*/ /*int p(int m) { int i,n=sqrt(m); for(i=2;i<=n;i++) if(m%i==0) break; if(i>n) return 1; else return 0; } main() {

int m; for(m=1;m<=10;m++) { if(p(m)) printf("%d ",m); } printf("\n"); }*/ //3-100间所素数。 /*main() { int i,n; for(n=3;n<=100;n++) { for(i=2;i<=n-1;i=i+1) if(n%i==0) break; if(i>=n) printf("%d\t",n); } }*/ /*main() { int i,m,j; for(i=2;i<=10;i++) { m=sqrt(i); for(j=2;j<=m;j++) { if(j%m==0) break; if (j>m) //加上这句，如果检查所有的j全部不能整除m，循环结束后，j一定大于m,这时的i才是素数 printf("%d",i); } } } /* void main() { int i,j,n=0,xx[10]; for(i=1;i<10;i++)

素数的几种判断方法和实现

PS：本来没有决心把这个东西写完的，结果早上写到一半，出去吃个饭，没保存，回来手一抖直接关掉了，好不容易写了一大半了，只能重新写了，坑爹啊，但就是这个插曲，本来还没有决心的我，一下子却坚定了信念，一点要把这个东西写完。就这样开始吧 BY：Lee 下面，我们重新开始 ═══════════════════════════════════════════ 如何判断一个数是否是素数呢 ═══════════════════════════════════════════也许你会认为这是一个简单的问题，但事实上，世界上任何一个问题，都没有你想象中的那么简单1 + 1 是否等于2 ，这便是一个简单而又复杂的问题，呵呵。 突然想把这个东西换一种风格来写了，就这样扯淡扯下去吧。扯的时候文章中多少有内容来自于网络，没有侵权的意思，如果作者看到还请见谅。 ═══════════════════════════════════════════下面正式进入正题 ═══════════════════════════════════════════ 一、朴素判断素数 ═══════════════════════════════════════════1. 这种方法被誉为笨蛋的做法： 一个数去除以比它的一半还要大的数，一定除不尽的，这还用判断吗？？ 很容易发现的，这种方法判断素数，对于一个整数n，需要n-2 次判断，时间复杂度是O(n)在n非常大或者测试量很大的时候，这种笨蛋做法肯定是不可取的。

2. 改进一下下小学生的做法： 3. 再改进一下聪明的小学生的做法 对于一个小于n的整数X，如果n不能整除X,则n必定不能整除n/X。反之相同一个明显的优化，就是只要从2枚举到√n 即可。 因为在判断2的同时也判断了n/2。到√n时就把2到n-1都判断过了。 在这里，这个聪明的小学生还用了i*i <= n 来代替sqrt（n）， 这里是避免了调用函数sqrt（），其消耗时间很大， 特别是在大量数据测试的时候消耗很明显。 这个算法的时间复杂度，与最前面的笨蛋做法就好多了， 不过这里好像用sqrt()也没问题啊，，，，这个就不太清楚了。 但是做一个测试发现，如果是这样额话，每一次判断都要计算i*i，

判断一个数是质数还是合数的方法

判断一个数是质数还是合数的方法 单位：平川区黄峤教管中心双铺中心小学张彦娟 一、质数和合数的意义： 质数：一个数只有1和它本身两个因数，这个数叫作质数。（除2以外所有的质数都是奇数。） 备注： 1、最小的质数是2。 2、既是偶数又是质数的数是2。 3、两个质数相乘的积一定是合数。 合数：一个数除了1和它本身以外还有其他的因数，这个数叫作合数。 备注: 1、最小的合数是4。 2、最大的一位合数是9。 3、1既不是质数，也不是合数。 二、判断一个数是质数还是合数有两种方法： 方法一：⑴判断一个数是质数还是合数需要看这个数的因数的个数，只有2个因数的数一定是质数，有3个或3个以上因数的数是合数。 ⑵个位上是0,2,4,6,8和5的数（除了0,2和5）一定不是质数，质数个位上的数字只能是1,3,7和9。 方法二：判断一个自然数是不是质数，可以用所有比它小的质数

从小到大依次去除它，除到商比除数小，而且还有余数，它就是质数，否则不是质数。 三、问题解析： 下面哪些数是合数？哪些数是质数？ 2 25 9 21 31 91 57 42 1、方法解析：因为除了1和它本身以外还有其他的因数的数是合数，所以先根据“2,5和3的倍数特征”来判断这些数除了1和它本身两个因数以外是否有因数2,5,3，如果有就为合数。 2和42有因数2，但2只有1和2两个因数，所以2是质数，42是合数。9,21,57有因数3，它们都是合数。25有因数5，也是合数。91有因数7，是合数。只有31除了1和它本身之外再没有其他的因数，所以31是质数。 2、解答：25,9,21，91,57,42是合数，2,31是质数。 四、100以内的质数： 100以内的质数有：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，共25个。

素数判断程序测试范例

问题描述：键盘输入m和n（10 #include using namespace std; int main() { int m,n,i; static int k=0; cout<<"输入m,m(其中10>m>>n; while(m<=10||m>=n||n>2000) { cout<<"输入数据有误，请再次输入："<>m>>n; } for(i=m;i<=n;i++) { int x=(int)sqrt((double)i); for(int j=2;j<=x;j++) { if(i%j==0) { break; } else if(j==x) { cout<

一．控制流测试1、控制流图如下:

2、根据以上控制流图： 因为控制流的1-2-3-2部分为用户输入的m,n的重复赋值过程，与输入数据密切相关且每次取值不同，关系到控制流测试，所以将此独立出来：以为节点“2”的复合谓词为或的关系，全为false时只有一种情况，而为true 时有7种情况，对“2”的复合谓词（m<=10||m>=n||n>2000）为真假时其表1如下： 设A:m<=10; B:m>=n; C:n>2000 但是对于节点“2”的情况，并非所有可能都会取到，因为当A为真时，就不会执行B，依此，生成下表2： 根据表2，得出此部分的取值及路径为：

密码学实验-素数判别

实验报告 实验七、素数判别 实验目的： 1、熟练掌握根据定义判定一个整数n是否为素数的方法及实现。 2、体会素数判定的时效性。 实验内容： 1、写出根据定义判定一个整数n是否为素数的算法及其实现。 2、判定101、10001、10000001、10000000000001是否为素数，并记录执行时间。 实验结果： 如果某个自然数n是素数，那么可能存在这样的情况—在2~n/2范围内没有一个自然数k能够整除n。所以，如果要判断自然数n是否为一个素数，只需要让n不断的去除以从2开始的，到n/2结束的整数k，这是一个反复执行的操作。如果在这个范围内的数没有一个k能够整除n，就说明n是一个素数。反之，只需要存在一个k能够整除n，就说明n不是一个素数。下面是我们对这个算法的分析： （1）首先输入一个需要判定的自然数n； （2）然后，将作为质数标志的字符串变量str的值设置为“是质数”； （3）接着，我们设置一个除数变量，同时也是一个计数变量k，将其初值设置为2； （4）使用第一个判断框，设置循环的条件为“k<=n/2”，因为除数变量k的最大取值不可能超过n/2； （5）使用第二个判断框，设置分支条件“n Mod k = 0”来判定自然数n能否被当前的除数变量k整除，如果条件不成立，则让除数变量k加1，然后返回到循环条件的判断框入口处，否则将质数标记字符串变量的值赋值为“不是质数”，再强行退出循环结构，输出变量str 的值，算法结束； （6）当正常退出循环结构后，也同样要输出质数标记字符串变量str的值，算法结束。对于本次实验，我们首先要把二进制转换成十进制素再利用上述算法判断是否为素数。 运行程序如下所示： #include #include

判断一个数是否为素数(c语言)

在C语言中，我们经常会用到判断一个数的性质，今天就以如何判断一个数是否为素数为例来说明思路，希望能够达到触类旁通的效果。 1.直接判断一个数是否为素数，代码如下： /* 目的：判断一个数是否是素数 */ # include int main(void) { int val; int i; scanf("%d",&val); for(i = 2; i < val; i++) // 用2到(val-1)的数去除val { if(val % i == 0) // 判断能否整除 break; } if (i == val) printf("YES!\n"); else printf("No!\n"); } 注：for循环的功能： ①若能整除，通过break跳出函数 ②若一直到val-1都不能整除，此时i再自增1到val，不满足i < val 跳出for循环，这时i = val。

2.通过函数来判断 /* 目的：通过函数判断一个数是否是素数 */ # include bool f(int m) { int i; for(i = 2;i < m; i++) { if(m % i == 0) break; } if(i == m) return true; else return false; } int main(void) { int val; scanf("%d",&val); if (f(val)) //注：此处若写成：if (f(val) == true) 也可以。 printf("YES\n"); else printf("NO\n"); } 对比上述两种方法可见，通过函数来实现比较合适，因为如果要判断的数据过多时，要通过第一种方法实现的话，代码太多，而且也不便于调用，因此推荐使用函数实现此功能。

判断质数还是合数游戏

1、填空题(分组进行，第一组王志义、第二组倪伊甸、第三组…………) 1、最小的偶数是几？ 2、最大的两位数，但是质数是（） 3、奇数加奇数的和乘偶数答案一定是（）数和（） 数。4、同时是2、3、5的最大两位倍数是（）。 是2的倍数叫（）数，不是2的倍数叫（）；自然数中最小的质数是（）；自然数中最小的合数是（）； 自然数中既是质数又是偶数的是（）； 20以内最大的奇数，但又是合数是（） 所有质数加1都会变成合数。（） 两个相邻的自然数中，有一个一定是质数或者是合数。 既不是质数也不是合数的数是（） 2、全班游戏。（全对的加2分，对3题、4题加一分，3题以下不加分） 1、请班级中是质数学号的人起立。 2、请班级中是合数学号的人起立。 3、请班级中是奇数和质数的学生起立。 4、请班级中是偶数又是质数的人起立。 5、请班级中是偶数又是合数的人起立。 3、全班游戏。（全对的加2分，对3题、4题加一分，3题以下不加分） 6、请班级中不是质数的人起立。 7、请班级中不是合数的人起立。 8、请班级中不是偶数但是合数的人站起来。 9、请班级中不是质数但是是奇数的人请起立。 10、请班级中不是奇数但是是质数的人请起立。 3、全班游戏。（重新编排编码0——9）猜一个电话号码，先全班写下来，停止时候，不在动笔，也请闭嘴。然后听好 老师要求，相关的学号学生站起来。然后，不正确的人就不加分，2分1题。 题目：第一个是2和3的最小公倍数，第二个数字是最小的偶数，第三个数字是最大偶数，第4个数字是最小的素数，第6个数字是它的质因数中只有3，第7个数字是5的倍数但是是质数，第8个数字是第3个数字的邻居，但是个质数。 4、抢答游戏，判断是质数还是合数（知道答案的直接起来报答案，报错口0.5分/次，对了加0.5分） 87 97 91 78 79 43 37 21 28 23 33 39 66 347 349 121 143 169 133 203 187 5、概念回答题（指名回答，抽背，每组抽2名，答对王志义组加分0.5分/次其余不加分，答错扣0.5分） 背诵什么是质数？什么是合数？质数的另外一个名字叫什么?(黑板上写) 填空：一个数的因数个数是（），倍数个数（）；一个数最小的因数是（）最大的因数（） 说出2的倍数的特征是（），说出3的倍数特征说出5的倍数特征 6、抢答游戏 猜两个数，猜好就请回答报答案（猜错扣1分/1次，猜对加1分） 1、这两个数的和是10、两个数的积是21； 2、两个数的和是20，两个数的积是91 3、两个数中，一个是最小质数，一个是最小合数。

质数判断

目录 摘要 (1) 1.方案论证 (2) 1.1．设计目的和要求 (2) 1.2．设计选题 (2) 1.3．总体方案 (2) 2 软件设计及说明 (3) 2.1主程序设计说明 (3) 2.2子程序流 (4) 2.2.1数字输入子程序 (4) 2.2.2质数判断子程序 (5) 3 程序段部分说明 (6) 3.1数据段定义 (6) 3.2主程序部分 (6) 3.3 子程序部分 (7) 3.3.1数字输入子程序 (7) 3.3.2质数判断子程序 (8) 3.4 DOS功能调用说明 (9) 4程序调试说明 (10) 5心得体会 (11) 参考文献 (12) 附录 (13)

摘要 汇编语言是面向机器的程序设计语言。在汇编语言中，用助记符代替机器指令的操作码，用地址符号或标号代替指令或操作数的地址，如此就增强了程序的可读性和编写难度。汇编作为一门语言，具有编程语言的一般特性，既有助于透彻的理解高级语言的核心原理，又能明晰程序内部的执行过程，更重要的是能够获得直接从底层分析问题解决问题的能力，为学习高层的知识奠定基石。 质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。因此我们可以对一个数不断的除以小于它的整数就可以得到结果，而用汇编语言实现这一点，需要灵活使用各种指令与结构，而输入输出还需调用一些dos功能以便打成目标。这些都有助于加深对汇编语言的理解。 关键词：汇编语言质数

质数判断汇编语言程序设计 1.方案论证 1.1．设计目的和要求 设计目的： （1）进一步建立微机系统的概念，加深对系统的理解和认识，培养学生应用微型计算机解决实际问题的能力； （2）进一步学习和掌握汇编语言程序的编写和应用的方法，通过较大规模程序的编写，提高编写汇编语言程序的水平和学习程序调试方法。 （3）进一步熟悉微机最小系统的构成及常用接口芯片的使用，提高系统设计能力。 设计要求：本次课程设计主要为软件设计选题，要求上机调试通过。 1.2．设计选题 质数判断汇编语言程序设计 要求：（1）提示输入数字；输入任意数字int1 ，点击Enter 结束输入； （2）如果int1 是质数，则输出“int1 is aprime number”；如果int1 不是质数，则输出“int1 is not aprime number”；点击Enter 程序退出；。 1.3．总体方案 质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。判断一个数N是否为质数可以用1到N（N>2）之间的N-2个数依次除N，若有能整除的则N为质数。由此可以知程序可分为三个部分：数字的输入，质数的判断，结果的输出。数字在输入时主要的任务是将输入的字符成功转变为数值然后存入寄存器中。质数的判断需要用循环语句来实现，将被除数n从2开始除直至判断出结果，然后输出。在写程序是质数的判断又与结果输出紧紧联系，故把这两部分程序放到一起。

c++,判断一个整数是否为素数用函数完成

实验七 一、实验内容 教材3.5 设计函数digit(num,k)，返回整数num从右边开始的第k位数字的值。例如：digit(4647,3)=6 digit(23523,7)=0 教材3.7 歌德巴赫猜想指出：任何一个充分大的偶数都可以表示为两个素数和。 例如：4=2+2 6=3+3 8=3+5 … … 50=3+47将4.50之间的所有偶数用两 个素数之和表示。判断一个整数是否为素数用函数完成。 教程例3 设计一个简单的计算器程序，从键盘输入“+3 5”代表表达式“3+5”，程序读入运算符和数据，调用Calculate（）函数，根据运算符进行加、 减、乘、除四则运算。要求能反复执行这一过程，直到用户输入“#” 符号作为运算符为止。 二、实验目的 1、掌握函数的定义调用方法。 2、掌握函数参数的传递（传值）、形参与实参的关系以及函数声明。 3、理解局部变量的作用。 三、实验步骤 教材3.5设计函数digit(num,k)，返回整数num从右边开始的第k位数字的值。例如：digit(4647,3)=6 digit(23523,7)=0 教材3.7 歌德巴赫猜想指出：任何一个充分大的偶数都可以表示为两个素数和。 例如：4=2+2 6=3+3 8=3+5 … … 50=3+47将4-50之间的所有偶数用两 个素数之和表示。判断一个整数是否为素数用函数完成。 教程例3 设计一个简单的计算器程序，从键盘输入“+3 5”代表表达式“3+5”，程序读入运算符和数据，调用Calculate（）函数，根据运算符进行加、 减、乘、除四则运算。要求能反复执行这一过程，直到用户输入“#” 符号作为运算符为止。 四、实验数据及处理结果 教材3.5 #include using namespace std; int main(){ int k,num,i=0,j,m; int digit[10]; cout<<"请输入正整数:"<<'\t'<<"右边开始第k位"<>num>>k; do{ digit[i]=num%10;

C++判断素数

C++判断质数 (1) #include void main() { int n,k; cout<<"please enter a number"<>n; for(k=2;k=n) cout<<"this is a zhishu"<=n) cout<<"this is a zhishu"<

(2) #include #include using namespace std; int main() { int x; while(cin>>x) //不知道这x=0时怎么不跳出循环{ if(x==0) break; int t=1; if(x<2) cout<<"非素数"<

#include using namespace std; int main() { int prime(int); int n; cout<<"please enter an integer:"; cin>>n; if(prime(n)) cout<

C语言素数的判定

几种简单的判断素数的方法 2009年05月12日星期二下午 10:34 素数还有很多东西需要学，先整理三种最简单的判断素数的方法，以后再深究补充。 判断n是否为素数 1、最简单的方法 用n除以2-sqrt(n),有一个能除尽就不是素数，否则是素数。 时间复杂度：O(sqrt(n)) 2、素数判断法： 这种方法是对上面方法的改进，上面方法是对2-sqrt(n)之间的数进行判断是否能除尽，而因为有如下算术基本定理，可以减少判断量。 算术基本定理：又称为素数的唯一分解定理，即：每个大于1的自然数均可写为素数的积，而且这些素因子按大小排列之后，写法仅有一种方式。例如:6936 = 2^3×3×17^2，1200 = 2^4×3×5^2。 由算术基本定理知，任何合数都可分解为一些素数的乘积，所以判断一个数能不能被2-sqrt(n)之间的素数整除即可。但是必须知道2-sqrt(n)之间的所有素数。 3、筛选法 这种方法可以找出一定范围内的所有的素数。 思路是，要求10000以内的所有素数，把1-10000这些数都列出来，1不是素数，划掉；2是素数，所有2的倍数都不是素数，划掉；取出下一个幸存的数，划掉它的所有倍数；直到所有幸存的数的倍数都被坏掉为止。 要找出10000以为的所有的素数，则需要一个大小为10000的数组,将其所有元素设置为未标记 首先把1设置为标记，从2开始，标记所有是它倍数的数，然后对下一个没有标记的数进行标记它的倍数。 当标记完成后，所有未标记的数即为素数。 这种算法需要O(n)的空间，不要偶数，可以节省一半的存储空间，标记需要 O(n^2/logn)(我写的，不知道对不对),判断是否是素数只需要O(1)的时间。 贴一下程序代码： /* 2009.5.12 by HK */ #include #include #include

判断一个数是质数还是合数的方法

单位：平川区黄峤教管中心双铺中心小学张彦娟 一、质数和合数的意义： 质数：一个数只有1和它本身两个因数，这个数叫作质数。（除2以外所有的质数都是奇数。） 备注： 1、最小的质数是2。 2、既是偶数又是质数的数是2。 3、两个质数相乘的积一定是合数。 合数：一个数除了1和它本身以外还有其他的因数，这个数叫作合数。 备注: 1、最小的合数是4。 2、最大的一位合数是9。 3、1既不是质数，也不是合数。 二、判断一个数是质数还是合数有两种方法： 方法一：⑴判断一个数是质数还是合数需要看这个数的因数的个数，只有2个因数的数一定是质数，有3个或3个以上因数的数是合数。 ⑵个位上是0,2,4,6,8和5的数（除了0,2和5）一定不是质数，质数个位上的数字只能是1,3,7和9。 方法二：判断一个自然数是不是质数，可以用所有比它小的质数从小到大依次去除它，除到商比除数小，而且还有余数，它就是质数，

否则不是质数。 三、问题解析： 下面哪些数是合数？哪些数是质数？ 2 25 9 21 31 91 57 42 1、方法解析：因为除了1和它本身以外还有其他的因数的数是合数，所以先根据“2,5和3的倍数特征”来判断这些数除了1和它本身两个因数以外是否有因数2,5,3，如果有就为合数。 2和42有因数2，但2只有1和2两个因数，所以2是质数，42是合数。9,21,57有因数3，它们都是合数。25有因数5，也是合数。91有因数7，是合数。只有31除了1和它本身之外再没有其他的因数，所以31是质数。 2、解答：25,9,21，91,57,42是合数，2,31是质数。 四、100以内的质数： 100以内的质数有：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，共25个。