输出素数表，方法之一就是舍弃空间，换取时间，也就是用一个大数组来存放每一个数是不是素数。

这样用筛法求素，大大的减少了时间。

下面的筛法求素程序求（不输出，即不定义OUT）1亿以内的素数只需要十几秒的时间，远小于输出所需的时间。

这个程序用一个char数组来存放每一个奇数是不是素数的信息。

一个char是一个字节8位，存放8个数。

Program prime_char.cpp:
#include<iomanip>
#include<iostream>
#include<conio.h>
//#define DEBUG
#define OUT
using namespace std;
//常量定义
const long MAX=100000000;
const long CHAR_MAX=int(MAX/16+1);
const char byt[8]={128,64,32,16,8,4,2,1};
// 变量定义
/**********************************
prime saves whether n is a prime
the value of n is like:
prime[0]: 3, 5, 7, 9,11,13,15,17
prime[1]:19,21,23,25,27,29,31,33
**********************************/
unsigned char prime[CHAR_MAX];
// 函数声明
inline bool isprime(long);
inline void setcomposite(long);
void primeinitiate(void);
void out(long);
//函数定义
/****************************************
*Function main *
****************************************/
int main()
{
#ifdef DEBUG
test();
#else
long n,m;
primeinitiate();
n=5;
while(n*n<=MAX)
{
if (isprime(n))
{
#ifdef OUT
out(n);
#endif
m=int(MAX/n);
if (m%2==0) m--;
while(m>=n)
{
if (isprime(m)) setcomposite((m*n)); m-=2;
}
}
n+=2;
}
#ifdef OUT
for (;n<=MAX;n+=2)
{
if (isprime(n))
out(n);
}
#endif
#endif
cout << "OK";
getch();
return 0;
}
/****************************************
*Test function *
****************************************/ void test(void)
{
}
/****************************************
*Function primeinitiate *
*to initiate the array prime[] *
*input : nothing *
*output : nothing *
****************************************/ void primeinitiate(void)
{
long i;
for(i=0;i<CHAR_MAX;i++)
{
if (i==0) prime[i]=237; //11101101
else if(i%3==0) prime[i]=109; //01101101
else if(i%3==1) prime[i]=182; //10110110
else if(i%3==2) prime[i]=219; //11011011
}
}
/****************************************
*Function isprime *
*To know if we haven't been sure that *
* n is a composite *
*Input : n *
*Output : false if we are sure that n *
* is a composite; *
* ture if we aren't sure that n*
* is a composite; *
****************************************/
inline bool isprime(long n)
{
return ((prime[int((n-3)/16)] & byt[((n-3)%16)/2]) != 0); }
/****************************************
*Function setcomposite *
*To let us be sure that an integer is *
*a prime *
*Input : n *
*Output : nothing *
****************************************/
inline void setcomposite(long n)
{
prime[int((n-3)/16)] &= ~byt[((n-3)%16)/2];
// return UNCHECKED;
}
void out(long n)
{
static long i=0;
cout << setw(5) << setiosflags(ios::right)<< n << " ";
i++;
i%=100;
if (i%10==0) cout << endl;
if (i%100==0) getch();
}
(以上程序经过Dev-C++ 4.9.6.0编译通过)
很久以前编的程序，现在拿出来见见天日吧。