最速の素数判定アルゴリズム　　

メモリーが２５６メガくらいあれば動くみたい
MAXNに設定出来る最大は FFFFfffD だから注意して
#include <stdio.h>
#define MAXN 0x7FFFfffFU
static unsigned char *tbl;
void ClrTable(unsigned int n){
　 unsigned int a=n>>4U;
　 unsigned int bpos=1<<( (n>>1u) & 7u);
　 tbl[a]|= bpos; //0なら素数 1ならそうでない
}
bool TestTable(unsigned int n){
if (n&1){
　　 unsigned int a=n>>4U;
　　 unsigned int bpos=1<<( (n>>1u) & 7u);
　　 return 0== (tbl[a] & bpos);
　 }else
　 return (n==2);
}
main()
{unsigned n;
　 int SqrMAXN=0xFFFF;
　 for(int i=0;i<10;i++){int r=MAXN/SqrMAXN; SqrMAXN +=(r-SqrMAXN)/2;};
　 SqrMAXN++;

　 tbl=new unsigned char [1+MAXN/(8u*2u)];
　if (!tbl){ printf("ERROR\n");return 1;};
　 for(int i=0;i<MAXN/(8u*2u);i++)tbl[i]=0;
　 for(n=3;n<=SqrMAXN;n+=2)
　 if(TestTable(n) )
　 {　unsigned nn=n*n , n2=2*n;
　　 printf("%5u\n",n);
　　 for(unsigned i=nn;i<=MAXN;i+=n2)ClrTable(i);
　 }
　 for(;n<=MAXN;n+=2)
　 if(TestTable(n) )printf("%5d\n",n);
　return 0;
}