求质数的算法
根据素数的性质，代码设计如下：
设计一：判断n是否能被1~n-1整除，不能整除为素数
#include<stdio.h>
int main()
{
int i, n;
scanf("%d", &n);
for (i = 2; i < n ; i++)
{
if (n%i == 0)
break;
}
if (i < n) printf("This is not a prime.");
else printf("This is a prime.");
return 0;
}
设计二：判断n是否能被2~√n间的整数整除，不能整除为素数
#include<stdio.h>
#include<math.h>
int main()
{
int n,i;
double k;
scanf("%d", &n);
k = sqrt(n);
for (i = 2; i <= k;i++)
{
if (n%i == 0) break;
}
if (i <=k) printf("This is not a prime.");
else printf("This is a prime");
return 0;
}
(1)求质数的算法扩展阅读：
1.素数的定义是只能被1和他本身整除,1不是素数.因此要判断一个数是否为素数.就要判断它能不能被比他小的所有素数整除,这是一个算法.(写到算法时,我只能写出用它除以比他小的所有数,造成运算速度低下)
2.如果一个质数大于根号n，而n可以除尽它，那么n必然也可以除尽一个更小的质数。由此可以得到一个法2较快的素数判断算法
‘贰’ math：求质数的几种算法
你想想吧，如果判断100是否为素数，那就是用2、3、4……去除100，只要有一个被整除了，那100就不是素数！sqrt(100)是求100的平方根的意思，100的平方根是10，用2、3、4……10去除100就可以了，用不着再用11、12、13……99去除100了。为什么呢？因为一个数是它的两个平方根之积，用其中一个平方根之内的各个数遍历了，难道还有漏网的数未去除“这个数”？比如100吧，找个大于其平方根10的好说的数20为例，说没有必要用20去除100了就是因为你已经用5除过了，100不是素数！a÷b=c的话，那a÷c不就等于b嘛，干嘛非得反过来再除一次？这样做的目的是为了提高代码时效，试想10000的平方根是100，用这方法10000是不是素数顶多做100次除法就知道了，不然就可能要做9999次，哪个时效高？多说一句，从判定“是不是素数”这一点上说，有没有sqrt(这个数)倒确实是无意义的……
‘叁’ 如何算出一个数的所有质数
1、找到这个数字的平方根m=√m
2、找到不大于m的所有质数。
3、在一张自然数表上划掉所有质数的整数倍（质数本身不划掉）
4、把1划掉。
5、没有划掉的数字就是质数。
例如，我们要找到100以内的所有质数，只需要按照下面的步骤进行：
1、计算100的平方根，是10。
2、10以内的质数有2、3、5、7
3、划掉2、3、5、7的整数倍。首先划掉2的倍数，如4、6、8…、98、100，然后划掉3的倍数，如6、9、12、15、…、99， 重复的就不需要再划掉了。然后划掉5的倍数，7的倍数。
4、最后划掉1。
(3)求质数的算法扩展阅读
质数与黎曼猜想
我们之前谈到：质数与黎曼猜想之间有着千丝万缕的联系。1896年，法国科学院举行比赛：征稿证明黎曼定理。两位年轻的数学家阿达马和德·拉·瓦莱布桑获得了这一殊荣。
实际上这两位数学家并没有证明黎曼猜想，只是获得了一点进展，但是这一点进展就一举证明了欧拉和勒让德的猜想，把素数猜想变成了素数定理。黎曼猜想的威力可见一斑。
1901年，瑞典数学家科赫证明：如果黎曼猜想被证实，那么素数定理中的误差项c大约是√xln(x)的量级。
即便黎曼猜想被证实，人们也只是在质数规律探索的过程中更近了一步，距离真正破解质数的规律，还有很长的路要走。也许质数就是宇宙留给人类的密码。
‘肆’ 求质数方法
筛法求质数：
用筛法求质数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是质数，首先把它筛掉。剩下的数中选择最小的数是质数，然后去掉它的倍数。依次类推，直到筛子为空时结束。如有：
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
1不是质数，去掉。剩下的数中2最小，是质数，去掉2的倍数，余下的数是：
3 5 7 9 11 13 15 17 19 21 23 25 27 29
剩下的数中3最小，是质数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的质数为：
2 3 5 7 11 13 17 19 23 29
(4)求质数的算法扩展阅读：
质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中，将会因为找质数的过程过久，使即使取得信息也会无意义。
在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。。
参考资料：
网络--筛法求素数
‘伍’ 找出1－100之间的质数，该怎么设计算法
100以内的质数共有25个，这些质数我们经常用到，可以用下面的两种办法记住它们。
� 一、规律记忆法
� 首先记住2和3，而2和3两个质数的乘积为6。100以内的质数，一般都在6的倍数前、后的位置上。如5、7、11、13、19、23、29、31、 37、41、43……只有25、35、49、55、65、77、85、91、95这几个6的倍数前后位置上的数不是质数，而这几个数都是5或7的倍数。由此可知：100以内6的倍数前、后位置上的两个数，只要不是5或7的倍数，就一定是质数。根据这个特点可以记住100以内的质数。
� 二、分类记忆法
� 我们可以把100以内的质数分为五类记忆。
�第一类：20以内的质数，共8个：2、3、5、7、11、13、17、19。
�第二类：个位数字是3或9，十位数字相差3的质数，共6个：23、29、53、59、83、89。
�第三类：个位数字是1或7，十位数字相差3的质数，共4个：31、37、61、67。
�第四类：个位数字是1、3或7，十位数字相差3的质数，共5个：41、43、47、71、73。
�第五类：还有2个持数是79和97。
� 一种简便的试商方法
� 试商是计算除数是三位数除法的关键，当除数接近整百数时，可以用“四舍五入法”来试商，然而当除数十位上是4、5、6不接近整百数时，试商就比较困难，有时需要多次调商。为了帮助同学们解决这个困难，下面介绍一种简便的试商方法。
� 当除数十位上是4时，舍去尾数看做整百数。用整百数做除数得出的商减1后去试商。
� 命名如1944÷243，除数十位上是4，把243看做200，1944÷200商9，用8(9－1)去试商正合适。
� 当除数十位上是5、6时，舍去尾数向百位进1，把除数看做整百数，用整百数做除数得出的商加1后去试商。
� 例如：1524÷254除数十位上是5，把254看做300，1524÷300商5，用6(5＋1)去试商正合适。
� 运用上面这种试商方法，有的可以直接得出准确商，有的只需调商一次就行了。同学们不试在计算除法时试一试。
c++:输出1~100的质数
#include<iostream>
using namespace std;
int main()
{
int i, j;
for(i=1;i<=100;i++) {
for(j=2;j<i;j++)
if(i!=j&&i%j==0)
break;
if(i == j) cout<<i<<endl;
}
system("pause");
}
‘陆’ 求质数的最优算法
#include <stdio.h>
int main()
{ int i,j,t;
for (i=2;i<100;i++)
{ t=1;
for (j=2;j<i;j++) /找因数的范围可以是2到一半 或者平方根，甚至 可以 比平方根小的质数，当然要建一个数组
if (i % j ==0)
{ t=0;
break;
}
if (t==1)
printf("%d\n",i);
}
return 0;
}
‘柒’ c语言求质数的算法，讲方法也行，不要那种on2的算法
【小学生版】
判断 x 是否为质数，就从 2 一直算到 x-1。
【小学生毕业版】
稍微聪明一点的：x 如果有质因数，肯定会小于等于 x/2，所以捏，就从 2 一直到 x/2 即可。
这一下子就少了一半的工作量哦。
【初学生版】
再稍微聪明一点：除了2以外的质因数都是奇数。所以算从3开始一直到 x/2 的所有奇数。
这一下子，工作量又少了一半哦。
【高中生版】
再聪明的发现：其实只要从 2 一直尝试到【根号x】，就可以了。因为x只要有因数必定有一个因数小于等于根号x。
【本科生版】
机智的本科生：要是把初中学生+高中生=只要判断2到根号x之间的奇数⊙▽⊙
【本科毕业生版】
稍加机智的发现：其实，只要尝试小于根号x 的质数即可。而这些质数，恰好前面已经算出来了。于是会把已经算出的质数，先保存起来，然后用于后续的判断，效率就大大提高了。【空间换时间】
【之后的版本】我还没本科毕业⊙▽⊙。。。
‘捌’ python求质数的算法
很早 的一个 函数
‘玖’ 求 质数 的计算公式
质数公式
当N为正整数时，形如 （N！）N+1的数一定是质数
不信大家去验证看看！
在公式A=(n-1)*(¦¦B2-1¦-(B2-1)¦)/2+2, 其中B=m(n+1)-(n!+1)中，m,n以自然数代入，所得的结果一定是素数。 这就是自欧几里德在<<几何原本>>证明了素数是无限多个后，多少世纪以来人们一直所寻找的能写出所有素数的公式! 不难看出，A一定是整数，且有: 若B=0,有A＝n+1; 若B≠0, 有A=2. B≠0时，A已为素数，当B=0, 即m(n+1)-(n!+1)=0, 即m=(n!+1)/(n+1).在初等数论中有一着名的定理叫做"威尔逊定理", 可陈述为(n!+1)/(n+1)为整数的充要条件是n+1是素数。所以B=0时，m=(n!+1)/(n+1)为整数，故A＝n+1必为素数。
或尝试下面公式：
X取任意正整数,如对于下式ab没有正整数解时.6X+1或6X-1必为素数!(本式可给出所有素数,当1、2式无解时，6X+1为素数，当3、4时无解时，6X-1为素数，当X在1-4式均无解时，则6X+1、6X-1均为素数，同时也证明了孪生素数有无穷多的猜想成立，相反，凡X有解时，则上述均非素数)
(1)6ab+a+b=x
(2)6ab-a-b=x
(3)6ab+a-b=x
(4)6ab-a+b=x
‘拾’ 求 质数 的计算公式
摘要 P=(r1+1)×(r2+1)×(r3+1)×……×(rn+1)