求质数(Prime)
试编写一个程序，找出前N(如200)个质数。希望从所知的使用除法的方法中，用最快的方法。
【参考文献】
1986年1月与2月《微电脑时代》杂志上Micro随笔专栏中《求质数》这两篇文章
B.A.Chartres. Algorithm 310, Prime Number Generator, Communications of ACM. Vol.10(1967), pp.569
B.A.Chartres. Algorithm 311, Prime Number Generator, Communications of ACM. Vol.10(1967), pp.570
R.C.Singleton. Algorithm 356, Prime Number Generator, Communications of ACM. Vol.12(1969), pp.563
R.C.Singleton. Algorithm 357, Prime Number Generator, Communications of ACM. Vol.12(1969), pp.563-564
解答：
求质数有很多方法。用除法求质数一般都是给定一个2~N之间的数i，然后用2~i的平方根之间的数去除i。但是，这样很浪费时间。(1)可以先排除2的所有倍数，也就是所有的偶数。(2)同理，可以排除所有3的倍数。(3)用2,3,....i的平方根去除i也是很浪费的，因为如果2不能整除i，那么2的倍数肯定也不能整除i；3不能整除i，那么3的倍数肯定也不能整除i.....最理想的方法就是用比i的平方根小的所有质数去除。现在的问题就是，如何产生比i的平方根小的所有质数？可以准备一个数组prime[ ]，用来存放找出的质数，一开始应该有2、3、5。于是当i = 5，7，11，13，17，19，23，25，29，...这些不是2和3的倍数时，就用prime[ ]中小于i的平方根的数去除i即可。如果都除不尽，那么i就是质数，把i存入prime[ ]中。
任意连续的6个数字中，例如6n，6n+1，6n+2，6n+3，6n+4，6n+5，6n、6n+2、6n+4为偶数，6n+3为3的倍数，因此只需测试6n+1和6n+5是不是质数。观察5，7，11，13，17，19，...可以得出一个规律，相邻两个数之间的距离为2，4，2，4，...有规律的变化。可以设置一个变量gap=2，然后每次让gap = 6 - gap即可。
另外需要注意的是，用所有小于i的平方根的质数去除可能会有问题，例如121，由于平方根函数的返回值为double类型，可能得出的结果为10.99999，这样去除121得质数就只有2，3，5，7，得出的结果就是121是质数。可以反过来，如果某个质数的平方小于或等于i，那么就用该质数去除i，这样就不会出现上面的问题。
代码：
int prime(int N)
{
int *prime = malloc(sizeof(int) * N/6); /*array saving prime numbers*/
int count = 3; /*no need to verify 2, 3, 5*/
int candidate = 7; /*start from 7*/
int gap = 4; /*the next to verify after 7 is 11, 11-7=2*/
int i,is_prime;
prime[0] = 2;
prime[1] = 3;
prime[2] = 5;
while(candidate < N)
{
/*test whether candidate is prime number*/
is_prime = 1;
for(i = 0; prime[i]*prime[i] <= candidate && is_prime; i++)
{
if(candidate % prime[i] == 0)
is_prime = 0;
}
if(is_prime) /*candidate is prime number*/
prime[count++] = candidate; /*save to prime[ ]*/
candidate += gap;
gap = 6 - gap;
}
printf("===============================\n");
printf("There are %d prime numbers between 2 to %d:\n",count, N);
for(i = 0; i < count; i++)
{
if(i % 10 == 0) printf("\n");
printf("%4d",prime[i]);
}
free(prime);
return count;
}
下面是书中代码BAD.C
#include <stdio.h>
#define MAXSIZE 100
#define YES 1
#define NO 0
void main(void)
{
int prime[MAXSIZE];
int gap = 2;
int count = 3;
int may_be_prime = 5;
int i, is_prime;
prime[0] = 2; prime[1] = 3; prime[2] = 5;
while(count < MAXSIZE)
{
may_be_prime += gap;
gap = 6 - gap;
is_prime = YES;
for(i = 2; prime[i] * prime[i] <= may_be_prime && is_prime; i++)
if(may_be_prime % pime[i] == 0)
is_prime = NO;
if(is_prime)
prime[count++] = may_be_prime;
}
printf("\nPrime Number Generation Program");
printf("\n=========================\n");
printf("\nFirst %d Prime Numbers are: \n", count);
for(i = 0; i < count; i++)
{
if(i % 10 == 0) printf("\n");
printf("%5d", prime[i]);
}
}
思考问题：
(1)使程序跳过2、3、5的倍数也是可能的，请构想一个可以达成目标的算法。如果请问它有多复杂，值不值得写到程序中？如果用这个方法，程序可以快多少？
(2)BAD.C中把5放到prime[ ]中，请问这是不是多此一举？为什么？如果不这么做，有什么好建议？
(3)有人说，is_prime这个变量是多余的，其实也是如此。有没有办法修改这个程序，去掉is_prime呢？
解答：可以不用is_prime，改成
if(may_be_prime % prime[i] == 0) break; 即可。
后面的判断条件就是if(may_be_prime % prime[i])。
(好像感觉这样做会有问题？)
(4)BAD.C是用来求1－100之间的质数用的，但该程序的要求是尽可能的使循环的执行次数最少。请问BAD.C达到要求了没有？为什么？请列出所有的改良建议。
(5)修改程序，让它可以求出1~N(输入)间的所有质数。请问，如果程序改成读入M与N(M < N)求出M~N之间所有的质数时，程序的工作量可以少一些吗？为什么？
