Home > 算法研究 > [算法]用两种求质数的算法(穷举法,筛选法),C语言实现

[算法]用两种求质数的算法(穷举法,筛选法),C语言实现

今天考试的题目是记不得了,等题目公开了再给大家分析,今天讲点经典的算法,求质数,相信很多人还是记得当年的穷举法了吧,就是不断的让每一个数除以一个小于他的数最大到sqrt(N),然后得出结果,算法时间复杂度O(N^2),优化过的算法O(N * sqrt(N)),经典的算法我就不讲了,初学者如果不懂的话,可以留言,或者跟我联系


代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*求质数的经典方法,穷举法
*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++) {
   for(j = 2 ; j <= (int)sqrt(i) ; j++){/*比较直到j到sqrt(i)*/
     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,筛除完毕

具体算法如下:

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
/*筛选法求质数
*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<n +1 ; i++) {
        num[i] = i;/*待筛选数组赋值,这步简单但是非常重要*/
    }
    for(i = 2 ; i < N + 1 ; i++){
        j = 2;
        while(j * i < N + 1){/*不符合条件的数字筛除*/
            num[j * i] = 0;
            j++;
        }/*while*/
    }/*for*/
    for(i = 2 ; i < N + 1; i++) {/*输出*/
        if(num[ i ] != 0)
            printf("%-10d" , num[ i ]);
    }/*for*/
    return 0;
}/*main*/

Categories: 算法研究 Tags: , ,
  1. December 22nd, 2008 at 00:22 | #1

    贵站链接已经做好,(*^__^*) 嘻嘻……欢迎查看www.pc-study.cn

  1. No trackbacks yet.