求质数2012年12月29日

昨天太忙，没有时间做一个题，先记着，明天来补。

问题描述很简单，就是求N之内的所有质数并且打印出来。

思路:求质数有很多方法，我这里用一种比较高效的方法。我一步一步地说明方法。

1.比如判断一个数num是否为质数，那么就用num去对"i(i从2开始)直到根号num"取模，如果都不能整除就说明num是质数。

2.但是这样会有很多次多余的计算。从1到N，有很多数是可以直接被2,3整除了，那么，就需要去除掉能被2,3整除的数。在6个数里,6n+1,6n+2,6n+3,6n+4,6n+5,6n+6中，只有6n+1,6n+5需要被测试。

3.进一步地，将取模的范围缩小为"从1到根号num"范围内的质数。

代码如下:

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 #define MAX 10000
 5 #define YES 1
 6 #define NO 0
 7 
 8 //prototype
 9 int judge(int judge_num);
10 
11 int prime[MAX]={2,3,5};
12 int N=100;
13 int count=3;
14 
15 int main()
16 {
17     int index=0;
18     int num;
19     for(index=1;index*6+5<=N;index++) //Just test 6*n+1,6*n+5
20     {
21         num=6*index+1;
22         if(judge(num)==YES) 
23             prime[count++]=num;
24         num=6*index+5;
25         if(judge(num)==YES) 
26             prime[count++]=num;
27     }
28     for(index=0;index<count;index++)
29         printf("%d ",prime[index]);
30     printf("\n");
31 }
32 
33 int judge(int judge_num)
34 {
35     int index=0; 
36     for(index=0;prime[index]*prime[index]<=judge_num;index++)
37     {
38         if((judge_num%prime[index])==0) 
39             return NO;
40     }
41     return YES;
42 }

参考资料:《C语言名题精选百则技巧篇》

如果我的文章对你有帮助，请推荐一下，非常感谢!