质数的计算方法(质数的计算方法和公式)
怎么算质数?
15、16、18、20、21、22 、24 、25、26 、27 、28、30 、32、33、34、35 、36 、38 、39 40、42 、44、45 、46 、48 、49、50、51 、52、54、55、56、57、58、60、62、63、64 、65、66、68、69、70、72、74、75、76、77、78、 80、81、82、84、85、86 、87、88、 90 、91、92、93 、94、95、96 、98、99、100所谓质数或称素数，就是一个正整数，除了本身和 1 以外并没有任何其他因子。例如 2，3，5，7 是质数，而 4，6，8，9 则不是，后者称为合成数。从这个观点可将整数分为两种，一种叫质数，一种叫合成数。（有人认为数目字 1 不该称为质数）著名的高斯唯一分解定理。全文
123222
热心网友2019-03-25
质数: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合数:4、6、8、9、10、12、14、15、16、18、20、21、22 、24 、25、26 、27 、28、30 、32、33、34、35 、36 、38 、39 40、42 、44、45 、46 、48 、49、50、51 、52、54、55、56、57、58、60、62、63、64 、65、66、68、69、70、72、74、75、76、77、78、 80、81、82、84、85、86 、87、88、 90 、91、92、93 、94、95、96 、98、99、100所谓质数或称素数，就是一个正整数，除了本身和 1 以外并没有任何其他因子。例如 2，3，5，7 是质数，而 4，6，8，9 则不是，后者称为合成数。从这个观点可将整数分为两种，一种叫质数，一种叫合成数。（有人认为数目字 1 不该称为质数）著名的高斯唯一分解定理。
质数的算法
质数的定义
质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
这次我们的例题是：
求n以内的质数。（其中 n是传入的参数）。
这里我们介绍三种常见方法：
1.完全遍历法：
这种算法比较基本，对于每个数n，将n依次从2除到n，然后对余数进行比较，如果余数是0，则除得尽，如果不是0则除不尽，按照质数的定义，只有1和他本身能成为因数也就是除得尽，所以只有除得尽的数不大于两个时，才能是质数。
算法实现：
int n;
int count=0;
cinn;
for（int i =2;i=n;i++）{ //i从2开始相应了质数定义中的第一句话。
for(int j = 1;j=n;j++) //从1开始响应了质数定义中“除了1和其本身外没有其他因数的特点”
if(ij==0)
count++;
if(count ==2)
couti" ";
}
这种算法的好处是符合大多数人的第一反应，和定义契合得比较好，也比较省空间，但问题是假如我这里n输入了1000000+时，这个运算时间是非常长的，其算法复杂度高达1*10^12,小数据可以用遇到大数据就很难实现高效了。
开根号遍历法
仔细分析算法我们会发现，其实在做除法运算时不需要除每一个数，只要除到根号n即可。这是因为当除数大于根号n时，其结果肯定是小于根号n的（可以用反证法证明），假如此时能除得尽，那么该种可能早就在小于根号n的遍历中被排除掉了，就没有意义了。这样就减小了一部分算法复杂度。
算法实现：
int n;
int count=0;
cinn;
for（int i =2;i=n;i++）{ //i从2开始相应了质数定义中的第一句话。
for(int j = 1;j=sqrt(n);j++) //从1开始
if(ij==0)
{count++;
if(count==2)
break;
}
if(count ==1)
couti" ";
}
1
筛选法
筛选法的核心是牺牲内存换速度，因为其不通过遍历来表达一列数而是直接通过数组来表达。用静态的bool量去变现数的状态。
其核心流程为：
定义一个bool数组，其下标为我们要判断的数，其值为true。表示初始阶段所有数都假定是素数。
开始对这个数组进行筛选（及把值改为false），实现把因数含有2的所有数筛掉，把因数含有3的数筛掉，把因数含有5的数筛掉…一直筛选到只剩下素数为止。
这种方法的效率非常高，对于大小超过10万的数据非常好用，但是对于数据量为千万级的数来说，普通定义的数组是不够好用的，在实际调试中我们可以发现，当数据大于800万时，定义普通数组会报错。这时我们可以利用STL标准库中来定义数组。
#include vector
using namespace std;
vectorint sieve(int n); //函数声明,求n以内的质数
int main(int argc, char const *argv[])
{
? ? int n;
? ? cin n;
? ?
? ? vectorint ans = sieve(n);
? ?
? ? cout ans.size() endl;
? ? for (int i = 0; i ans.size(); i++) {
? ? ? ? cout ans[i];
? ? ? ? if (i ans.size() - 1)cout " ";
? ? }
? ? cout endl;
? ?
? ? return 0;
}
#includemath.h
vectorintsieve(int n){
? ? int j;
? ? vectorbool all;
? ? vectorint? shuju;
? ? for (int k = 0;k=n;k++)
? ? ? ? all.push_back(true) ;
? ? for(j=2;j=sqrt(n);j++){
? ? ? ? for(int i=2;i*j=n;i++)
? ? ? ? ? ? all[i*j] = false;
? ? ? ? }
? ? for(int i = 2;i=n;i++){
? ? ? ? if(all[i])
? ? ? ? ? ? shuju.push_back(i);
? ? }
? ? return shuju;
}
质数的公式是什么？
质数公式：
尽管整个素数是无穷的，仍然有人会问“100000以下有多少个素数?”，“一个随机的100位数多大可能是素数?”。素数定理可以回答此问题。
1、费马数2^(2^n)+1
被称为“17世纪最伟大的法国数学家”的费马，也研究过质数的性质。他发现，设Fn=2^(2^n)+1，则当n分别等于0、1、2、3、4时，Fn分别给出3、5、17、257、65537，都是质数，由于F5太大（F5=4294967297），他没有再往下检测就直接猜测：对于一切自然数，Fn都是质数。这便是费马数。但是，就是在F5上出了问题！
F5=4294967297=641×6700417，它并非质数，而是一个合数！
2、梅森质数
17世纪还有位法国数学家叫梅森，他曾经做过一个猜想：2^p-1 ，当p是质数时，2^p-1是质数。他验算出了：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2^p-1是质数。 p=2，3，5，7时，2^p-1都是素数，但p=11时，所得2047=23×89却不是素数。
3、算术基本定理
任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积 N=(P_1^a1)*(P_2^a2)......(P_n^an) , 这里P_1P_2...P_n是质数，其诸方幂 ai 是正整数。
这样的分解称为N 的标准分解式。
参见百度百科：
求质数方法
筛法求质数：
用筛法求质数的基本思想是：把从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
扩展资料：
质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中，将会因为找质数的过程过久，使即使取得信息也会无意义。
在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。。
参考资料：
百度百科--筛法求素数
质数是怎么算出来的？
质数是通过因式分解算出来的，质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数的数称为质数。
素数就是质数，即除了1和它本身以外任何数都不能整除他的数
素数可以这样算出来：将你知道的素数全部乘起来再加一。
比如你知道2是质数，3是质数，你可以得到质数2 X 3 + 6 = 7这个质数，你知道2是质数，3是质数，5是质数，可以得到2 x 3 x 5 + 1 = 31 这个质数
拓展资料
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
关于素数，有一个常为人所知的的著名问题，即哥德巴赫猜想。素数因其特殊性在计算和数理分析中占有重要地位。
求 质数 的计算公式？
质数公式
当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