下面以求1000000以内的素数为例,介绍几种求素数的方法。int prime[N]为所求结果存放的数组。
1. 根据概念求解
void makePrime(){
int i,j,k=0;
bool flag = true;
for(i=2;i<N;i++){
for(j=2;j<=i;j++){
if(i%j == 0){
flag = false;
break;
}
}
if(flag){
prime[k++] = i;
}
flag = true;
}
}
2. 在(1)的基础上缩小范围
根据定理:如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d
void makePrime(){
int i,j,k=0;
bool flag = true;
for(i=2;i<N;i++){
for(j=2;j<=sqrt(i);j++){
if(i%j == 0){
flag = false;
break;
}
}
if(flag){
prime[k++] = i;
}
flag = true;
}
}
3. 在(2)的基础上除去偶数
void makePrime(){
int i,j,k=1;
prime[0] = 2;
bool flag = true;
for(i=3;i<N;i++){
for(j=3;j<=sqrt(i);j+=2){
if(i%j == 0){
flag = false;
break;
}
}
if(flag){
prime[k++] = i;
}
flag = true;
}
}
4. 用6N±1法求素数
任何一个自然数,总可以表示成为如下的形式之一:
6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)
显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数)。
根据上述分析,我们可以构造另一面筛子,只对形如6 N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。
例如在(3)的基础上改进算法:
void makePrimes2(){
int i,j,k=1;
prime[0] = 2;
bool flag = true;
for(i=3;i<N;i++){
if((i+1)%6 == 0 || (i-1)%6 == 0){
for(j=3;j<=sqrt(i);j+=2){
if(i%j == 0){
flag = false;
break;
}
}
if(flag){
prime[k++] = i;
}
flag = true;
}
}
}
5.厄拉多塞筛法求素数
简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家,他在寻找素数时,采用了一种与众不同的方法:先将2~N的各数写在纸上。在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数 是5,将它画圈,并划去5的其他倍数……依次类推,一直到所有小于或等于N的各数都画了圈或划去为止。这时,表中画了圈的以及未划去的那些数正好就是小于 N的素数。
这很像一面筛子,把满足条件的数留下来,把不满足条件的数筛掉。
void makePrimes(){
bool flag[N]; //额外申请的空间用于标记素数,false为素数,true为非素数
int i,j,num = 0;
flag[2] = flag[3] = false;
for(i = 2; i < N; ++i){
if(!flag[i])
prime[num++] = i;
for(j=0; (j<num && i*prime[j] < N);j++){
flag[i*prime[j]] = true;
}
}
}
这种方法在时间上比上几种求法都高效,不过需要额外申请空间。
分享到:
相关推荐
自定义函数求素数(质数).py
用开方根的方法求素数,简单浅显易懂。适于初学者
java求素数的经典算法java求素数的经典算法java求素数的经典算法java求素数的经典算法
求素数的C语言版本 求素数的C语言版本 求素数的C语言版本
java 求质数实例程序 求质数 源代码 简单易懂
用C语言开发的求素数,适合初学者学习,参考价值比较大
java语言实现求素数的原根的源代码 输入一个素数 求出他所有的原根 密码学相关 java语言实现求素数的原根的源代码 输入一个素数 求出他所有的原根 密码学相关
c++关于用C++求素数的源程序
最快求素数的算法,求100000000以下所有素数0.3秒 , 在10000000以下的数中找到664579个素数,耗时53毫秒
Console.WriteLine("请输入数字:"); int x; //输入的数字 x = Convert.ToInt32(Console.ReadLine()); DateTime da = DateTime.Now; 。。。。。
用厄拉多塞法求素数的C源代码
利用动态规划思想求素数,线性时间内即可求解,可以处理指定数字()下的所有质因数
数组筛选法求素数c++编程
在VS环境下 在窗体中求素数 编写的语言是C#
如何求素数,并且用vb现实,这个是本程序所要设计的
这是一个用java编写的控制台程序,可以求一个数是不是质数,并且把这个数按递减顺序求,一直求到1,一次性的显示判断
并行计算求素数个数包括java、OpenMP、MPI、.NET、MFC、Windows Api等方法 并行计算求素数个数包括java、OpenMP、MPI、.NET、MFC、Windows Api等方法
利用筛法求素数利用筛法求素数利用筛法求素数利用筛法求素数利用筛法求素数
线性筛法求素数的原理与实现
Eratosthenes筛选法求质数.rar