代码如下：
/*求质数的经典方法，穷举法
*author CG
*2008 12 21
*时间复杂度O(N*sqrt(N))
*/
#include"stdio.h"
#include"math.h"
#define N 200/*定义测试数据*/
int main() {
int i , j;
for(i = 2 ; i < N i br>
for(j = 2 ; j < intsqrti jjsqrtibr>
if(i % j == 0){
break;
}/*if*/
}/*for*/
if(j > (int)sqrt(i)){/*符合条件？*/
printf("%-10d",i);/*输出*/
}/*if*/
}/*for*/
return 0;
}/*main*/
下面是目前使用得比较多的求质数的方法，当然更加优越的算法利用《费马小定理》
可以得出质数的概率分布实现接近线性的算法复杂度的，今天不讲，有兴趣？那继
续关注我吧，要是最近有时间的话，我会把代码放上来。
好了，今天的主角：筛选法求质数 ，原理就是从已经存在的数组数据中筛选要的质
数，需要一个N大小的空间，N为所求质数的范围，相比经典算法比较浪费，不过效
率较高，O(N*LogN)，适合大范围求质数，但是空间浪费也是客观的，
原理：从索引j=2,0,1,的情况排除了，开始筛除j的所有倍数，然后再筛j+1，直到
筛选到j=N,筛除完毕
具体算法如下：
/*筛选法求质数
*author CG
*2008 12 21
*算法复杂度O(N*LogN)
*/
#include "stdio.h"
#define N 200/*定义最大数*/
int main() {
double s , t;
int num[ N + 1 ] = {0};
int j = 2 ;/*定义起始数，从2开始*/
int i ;/*计数器*/
for(i=2 ; i
num[i] = i;/*待筛选数组赋值,这步简单但是非常重要*/
}
for(i = 2 ; i < N ibr>
j = 2;
while(j * i < N br>
num[j * i] = 0;
j++;
}/*while*/
}/*for*/
for(i = 2 ; i < N i br>
if(num[ i ] != 0)
printf("%-10d" , num[ i ]);
}/*for*/
return 0;
}/*main*/
--------------------------------------------------------------------------------------
- 版权声明：
- 如在本页面内无特别说明，本文内容均为[*博客]原创，本文版权归[*博客]所有。
- 欢迎转载，转载请务必在文章页面明显位置提供原文链接并注明出处。欢迎您在转载本文时保留本段声明。
- 文章标题： [算法]两种求质数的算法(穷举法，筛选法)，C语言实现
- 独立博客： *博客
- 永久链接：http://www.lidaren.com/archives/244
--------------------------------------------------------------------------------------
以上内容由博客自动发布工具自动发布，最终显示内容和效果会与原文内容有所偏差，敬请谅解。