用C语言编程求:n以内素数的个数（n<10^8）

当n=10^8时，要求三分钟以内完成
kevint2007的答案 3分钟使出不来的，要4个多小时

---

首先肯定要定义成long 型了
这个n 从以下几方面进行处理：
1：偶数者除了2以外均不是，任务将缩短一半 可采用 n+=2实现
2：最后一位是5的除了5以外不是素数，任务在1的基础上缩短1/5
3：在判断能被3及根号或一半n之间的数据时，也采用全用质数的方法i+=2 以及除去尾数是5的数。这样在每个n值下，检测不能被i整除的任务将缩短1/2+1/5即7/10。
4：对于数据较大的n可以采用位运算、移位运算、加法运算将其十进制时各位数字之和除以3，能整除者不是素数。
建议采用三级处理1-10 10-100 000 100 000-100000000分别编腔腔谈制程序段采用不同方伍碰法实现。
1-10 ：简单处理
1 0-100 000：采用1，2，3（i采用3——n/2）
100 000-100000000：采用1，2，3（i采用3——根号n）,4

“warmwormn - 举人 五级
。。。。。。。
筛选
每次把质数的倍数全部删除
只有循环和加法
”

综观不如楼上的方法（但实现很麻烦，并且表达不对）：如下
1定义一个素数存储数组a：
2每一个n(>2),除去偶数，只要将已经存在在a中数据进行组合相乘，均不与当前n相等的话，则n 为素数，存入a 中
3当然在组合过程中，
!: 明显小于前一个n时，可舍去不再比较,也不再累计到下一个n的比较。
!!:大于当前n及其后面的组合可舍去不再比较，但需要累计到下一个n的比较。
只有圆橡利用了这种方法，才有可能，降低运算工作量

---

写了一个，连写文件也只用13秒.
nCount=5761455
Time=13s

#include <stdio.h>
#include <time.h>
void main()
{
time_t tBegin;
time(&tBegin);
time_t tEnd;

int nMax=100000000;
bool *pByte=new bool[nMax+1];//此外多缺睁分配一个0空着不用.
int i=0,j=0;
int nCount=0;
if(pByte==NULL)
{
printf("内存分配失败！");
}

//先假设所有的数模衡都是素数
for(i=0;i<nMax;i++)
{
pByte[i]=true;
}

pByte[0]=false;//0不是素数
pByte[1]=false;//1不是素数
pByte[2]=true;//2是素数

//筛选,所有偶数都不是素数(除2以外旦扮做)
for(i=4;i<nMax;i+=2)
{
pByte[i]=false;
}

//筛选所有素数的整数倍都不是素数
for(i=3;i<nMax;i++)
{
if(pByte[i])
{
j=i;
while((j+=2*i)<nMax)
{
pByte[j]=false;
}
}
}

//输出结果
FILE *file;
if( (file = fopen( "Test.txt", "a" )) == NULL )
{
printf("打开文件出错.");
return;
}

nCount=0;
for(i=2;i<nMax;i++)
{
if(pByte[i])
{
::fprintf(file,"%d\n",i);
nCount++;
}
}
fprintf(file,"nCount=%d\n",nCount);
time(&tEnd);
fprintf(file,"Time=%ds\n",tEnd-tBegin);
fclose( file);
delete [] pByte;
}

---

。。。。。。。
筛选
每次把质数的倍数全部删除
只有循环和加法

-----写了一个，没有验证还 P4-M 2.0 大约二十几秒吧------
100以内的好象没有问题
// n.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
int nMax = 100000000;
int i, j;
char *p = reinterpret_cast<char*>(malloc(nMax+1));//记录质数列表，下标为该数，镇芹为了相对应所以＋1
FILE *fp;

//初始化，默认都是质数
for( i = 0; i < nMax + 1; i++ )
{
p[i] = 1;
}

p[1] = 0;//知道1不是质数

//从2开始
for( i = 2; i <= nMax; i++ )
{
//如果这个数是质数，则将列表中该数的倍数全部清空
if( p[i] == 1 )
{
for( j = 2*i; j <= nMax; j+=i )
{
p[j] = 0;
}
}
}

fp = fopen( "c:\\test.txt", "w" );
for( i = 1; i <= nMax; i++ )
{
if( p[i] == 1 )
{
fprintf(fp, "%d\n", i );
}
}
fclose(fp);

system( "PAUSE" );

return 0;
}

---------------------------
denning的算法本质不就是筛选嘛？
只不过进行一定的筛选后，再进行传统单质数的算法
不过这一定快嘛？也许算法复杂比筛选法低，但在实际运行中
模余乘法 和 加法的指令周期是不一样的腊旅掘，更不要说是模余轮核了
同时如果通过组合相乘的话，其复杂度为2^n次方，即有N个质数
就要进行2^n次的比较
而且为了实现算法加入了更多的分枝，使用CPU命中率降低了
所以在总时间上应该不会比筛选法更优

---

main()
{
for(i=1;i<=sqrt(n);i++)
{
for(j=2;j<i;j++)
if(i%j<裤核旅胡凳>0) a[s++]=i;
}
for(i=1;i<氏铅=s;i++)
printf(%d,a[i]);
}
定义部分略

---