素数算法（c语言）求快速算素数的方法。

素数算法时间:2021-06-14 阅读:()

求一个判断素数的算法

#include<iostream> using namespace std; void main() { int n,i=0; cin>>n; for(int j=1;j<=n/2;j++) { if(n%j==0) { i++; } } if(i==0) cout<<"YES"<<endl; else cout<<"NO"<<endl; }

c语言素数的算法

思路如下： 1、求2-n之间的所有素数 2、创建一个数组a[n+2]，其下表为2...n+1 3、数组的功能是记录那些数十素数,其下标表示素数,元素初始化时全为1，表示全部数假设都是素数 4、从2开始往后访问数组的每一个元素，如果这个数十素数就输出，否则往后遍历 5、遍历的同时如果这个数i是素数，则进一步往后将这个数的倍数2*i，3*i，....将这些数都标记为0表示不是素数 6、执行完毕将输出所有素数了

新手求教 c语言素数判断算法

网上的代码意思是：n就是你输入的任意数，判断它是否是素数的方法是用大于2小于n的数去除n，若能整除即不是素数，跳出循环；若数一直增加到n+1都没有被整除，即可输出“素数”。

你的源程序：3是素数，很简单，所以用if来提醒输入大于3的数，你的只是另一种素数算法，是优化的算法，更快。

因为只需用2到根号a去判断。

计算素数的公式？

素数计算公式：素数计算公式,分为通用素数计算公式和对同一尾数的素数计算公式。

这里的计算除特殊素数2和5。

①、通用素数计算公式，是如何计算M之内有多少素数及具体素数的公式。

M≥7，具体步骤如下： M内有多少个奇数：4M/10-1+M的尾数奇数个数，减1为奇数1不参与，4M/10取整数。

素数3的删除数：M/3 其余单一素数的删除数：素数7的删除数，M/7≈N，为7—N的素数个数；素数11的删除数：M/11=N1，为11—N1的素数个数；素数13的删除数：M/13=N2，为13—N2的素数个数；……。

多个素数的删除个数：从素数7开始进行计算，多个素数之间的积，在M之内的。

素数个数=奇数个数-上面所有的删除个数+2。

这里加上的2为特殊素数2和5。

具体的素数计算，只需要把上面的方法，奇数进行实际排列，删除数该乘的一个一个乘出来，进行具体删除后，剩余的数字就是素数。

②、同一尾数的素数计算公式，我们在计算“哥德巴赫猜想”（1+1）时常常用到。

具体方法如下： M内有多少同一尾数的奇数：M/10，素数3的删除个数：M/30，其它单一素数的删除个数：素数7的删除个数，为7至M/70的素数尾数与7的乘积，与要求的奇数尾数一致的素数个数；素数11的删除个数，为11至M/110的素数尾数与1的乘积，与要求的奇数尾数一致的素数个数；素数13的删除个数，为13至M/130的素数尾数与3的乘积，与要求的奇数尾数一致的素数个数；……。

多个素数的删除个数：也是从素数7开始，多个素数的乘积与奇数尾数一致的个数。

素数个数=奇数个数-上面所有的删除个数。

具体的素数计算，只需要把上面的方法，奇数进行实际排列，删除数该乘的一个一个乘出来，进行具体删除后，剩余的数字就是素数。

生成素数表的算法有哪些

筛选法求素数表，最快的素数表生成算法。

所谓“筛选法”指的是“埃拉托色尼(Eratosthenes)筛法”。

他是古希腊的著名数学家。

他采取的方法是，在一张纸上写上1到100全部整数，然后逐个判断它们是否是素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。

具体做法如下： <1> 先将1挖掉(因为1不是素数)。

<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。

<3> 用3去除它后面的各数，把3的倍数挖掉。

<4> 分别用4、5…各数作为除数去除这些数以后的各数。

这个过程一直进行到在除数后面的数已全被挖掉为止。

例如找1～50的素数，要一直进行到除数为47为止（事实上，可以简化，如果需要找1～n范围内素数表，只需进行到除数为n^2(根号n)，取其整数即可。

例如对1～50，只需进行到将50^2作为除数即可。

）如上算法可表示为： <1> 挖去1; <2> 用刚才被挖去的数的下一个数p去除p后面各数，把p的倍数挖掉; <3> 检查p是否小于n^2的整数部分（如果n=1000, 则检查p<31?），如果是，则返回(2)继续执行，否则就结束; <4> 纸上剩下的数就是素数。

参考链接：/uid-9078996-id-2010292.html

（c语言）求快速算素数的方法。

//规模较大时，筛选法确实比较快 #include #include using namespace std; #define MAX_NUM 1000000 #define MAX_N 10000000 int main() { int *P; bool *B; int M, N, i, j, t, sqrtN; bool flag; P = (int *)malloc(sizeof(int)* MAX_NUM); B = (bool*)malloc(sizeof(int)* MAX_N); for (i=0;iMAX_NUM) { cout<<"too large"<

展开全文