试编写一个程序，找出2->N之间的所有质数。
希望用尽可能快的方法实现。
【问题分析】：
这个问题可以有两种解法：一种是用“筛子法”，另一种是从2->N检查，找出质数。
先来简单介绍一下“筛法”，求2~20的质数，它的做法是先把2~20这些数一字排开：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
先取出数组中最小的数，是2，则判断2是质数，把后面2的倍数全部删掉。
2 |
3 5 7 9 11 13 15 17 19
接下来的最小数是3，取出，再删掉3的倍数
2 3 | 5 7 11 13 17 19
一直这样下去，直到结束。
筛法求质数的问题时，非质数的数据有很多是重复的。
例如，如果有一个数3×7×17×23，那么在删除3的倍数时会删到它，删7、17、23时同样也会删到它。
有一种“线性筛法”，可以安排删除的次序，使得每一个非质数都只被删除一次。
从而提高效率。
因为“筛法”不是我要介绍的重点，所以就不介绍了。
现在我来介绍第二种方法。
用这种方法，最先想到的就是让从2~N逐一检查。
如果是就显示出来，如果不是，就检查下一个。
这是正确的做法，但效率却不高。
当然，2是质数，那么2的倍数就不是质数，如果令i从2到N，就很冤枉地测试了4、6、8……这些数？所以第一点改建就是只测试2与所有的奇数就足够了。
同理，3是质数，但6、9、12……这些3的倍数却不是，因此，如果能够把2与3的倍数跳过去而不测试，任意连续的6个数中，就只会测试2个而已。
以6n,6n+1,6n+2,6n+3,6n+4,6n+5为例，6n,6n+2,6n+4是偶数，又6n+3是3的倍数，所以如果2与3的倍数都不理会，只要测试的数就只留下6n+1和6n+5而已了，因而工作量只是前面想法的2/6=1/3，应该用这个方法编程。
还有个问题，就是如果判断一个数i是否为素数。
按素数的定义，也就是只有1与本身可以整除，所以可以用2~i-1去除i，如果都除不尽，i就是素数。
观点对，但却与上一点一样的笨拙。
当i>2时，有哪一个数可以被i-1除尽的？没有，为什么？如果i不是质数，那么i=a×b，此地a与b既不是i又不是1；正因为a>1，a至少为2，因此b最多也是i/2而已，去除i的数用不着是2~i-1，而用2~i/2就可以了。
不但如此，因为i=a×b，a与b不能大于sqrt(i),为什么呢？如果a>sqrt(i),b>sqrt(i),于是a×b>sqrt(i)*sqrt(i)=i，因此就都不能整除i了。
如果i不是质数，它的因子最大就是sqrt(i)；换言之，用2~sqrt(i)去检验就行了。
但是，用2~sqrt(i)去检验也是浪费。
就像前面一样，2除不尽，2的倍数也除不尽；同理，3除不尽，3的倍数也除不尽……最理想的方法就是用质数去除i。
但问题是这些素数从何而来？这比较简单，可以准备一个数组prime[]，用来存放找到的素数，一开始它里面有2、3、5。
检查的时候，就用prime[]中小于sqrt(i)的数去除i即可，如果都除不尽，i就是素数，把它放如prime[]中，因此prime[]中的素数会越来越多，直到满足个数为止！
不妨用这段说明来编写这个程序，但是程序设计的时候会有两个小问题：
1.如果只检查6n+1和6n+5？不难发现，它们的距离是4、2、4、2……所以，可以先定义一个变量gab=4，然后gab=6-gab;
2.比较是不能用sqrt(i)，因为它不精确。
举个例子，i=121，在数学上，sqrt(i)自然是11，但计算机里的结果可能是10.9999999，于是去除的数就是2、3、5、7，而不含11，因此121就变成质数了。
解决这个问题的方法很简单，不要用开方，用平方即可。
例如，如果p*p<=i，则就用p去除i。
而且它的效率比开方高。
【程序清单】：
#include <stdio.h>
int creat_prime(int prime[],int n,int total)
{
register int i;
register int j;
register int gab=2;
register int count;
for(i=7;i<=n;i+=gab)
{
count=1;
gab=6-gab;
for(j=0;prime[j]*prime[j]<=i;j++)
{
if(i%prime[j]==0)
{
count=0;
break;
}
}
if(count)
{
prime[total]=i;
total++;
}
}
return total;
}
int main(void)
{
int prime[30000]={2,3,5};
int total=3;//找到素数的个数
int i;
int n=200000;//要查找的范围(>=6)
total=creat_prime(prime,n,total);
for(i=0;i<total;i++)
{
printf("%d ",prime[i]);
if(i && !(i%10))
putchar('\n');
}
putchar('\n');
}
如果你有VC++或其他C编译器，可以去运行一下。
你会发现，会有很多时间去输出。
我给个小提示，
假设你编译生成的可执行文件是prime.exe，目录在D:\
那你在命令行下进如D:\然后输入命令 prime >1.txt
这样就可以把结果保存到1.txt。
你会发现在int越界的前提下，它几乎都是瞬间完成的！
当然这段程序还是有可以改进的地方，如果你有更好的建议，请联系我。
redraiment@
#include "stdio.h"
#include "conio.h"
main()
{ int m,n,i,num;
int p[100];
long s;
s=2;
m=1;
n=1;
num=1;
p[1]=2 ;
for (;num<100;num++);
{for (i=1,m=2;;)
{m=p[i] ;
if (m>s/2) break;
else if(m*n<s) n++ ;
else if (m*n==s) s++ ;
else if(m*n>s)i++ ;
}
printf ("p%d=%ld",num,s);
s++;
}
getch();
}
自己写的，感觉没有问题
运行结果总是：
p100=2
郁闷~~~
求错
问题补充：
哦~~被wintc的提醒弄狂了~~
是这样的
我用p[i]是想表示第i个质数
貌似这样有问题？？
请问还有救吗？
能不能实现类似的定义？？？
最佳答案
有救！有救！
你的思路挺好的，就是编程的时候思路不清晰，没有周全考虑。
这是改后的代码
#include "stdio.h"
#include "conio.h"
main()
{ int m,n,i,num;
int p[100];
long s;
s=2;
m=1;
n=1;
num=1;
p[1]=2 ;
for (;num<100;num++)/*这里的分号应该是你笔误吧O(∩_∩)O*/
{for (i=1,n=2;;) /*这里n=2而非m估计也是你笔误？*/
{m=p[i] ;
if (m>s/2) break;
else if(m*n<s) n++;
else if(m*n==s) {s++;i=1;n=2;}/*这里*/
else if(m*n>s) {i++;n=2;}/*和这里，仔细想一想，当尝试一个新的数字或尝试一个新的质数时，是不是要把计数变量初始化？*/
/*编程的时候不要想当然，要通盘考虑，每个变量是否都做了妥善的处理*/
}
p[num]=s;/*你要用质数表，怎么能不记录质数表呢^o^*/
printf ("p%d=%ld\n",num,s);
s++;
}
getch();
}
你的程序运用质数表这点很好，但是你的程序还没发挥到最高效率。
里边有一些无用的判断和赋值，而且没有利用mod运算，使程序既复杂又低效。
我觉得还是用标准的求质数算法比较好，到处都有，不再说了。