生成好了质数表, 这里可以下载(解压后的MD5为5D137D5D842AB468D7980F0FEE6D0872, 你也可以根据MD5计算出这512MB的文件)。
如下是参考程序, 它首先将文件读入内存(如果内存不够大, 请直接在readBool使用fd替换buf)。
随便写了个计时程序, 不准确。
#include<fcntl.h> #include<unistd.h> #include<cstring> #include<iostream> #include<sys/time.h> using std::cin; using std::cout; using std::endl; typedef unsigned long long uint64; #define UINT32_MAX 0x100000000L #define UINT32_MAX_SQRT 0x10000L void writeBool(int fd, uint64 pos, bool b) { if (pos<0 || pos>UINT32_MAX) { return; } char buf; lseek(fd, pos>>3, SEEK_SET); size_t len=read(fd, &buf, 1); //if not set yet if (len<=0) buf=0; if (b) buf |= 1<<(pos % 8); else buf &= ~(1<<(pos % 8)); lseek(fd, pos>>3, SEEK_SET); write(fd, &buf, 1); } bool readBool(int fd, uint64 pos) { if (pos<0 || pos>UINT32_MAX) { return false; } char buf; lseek(fd, pos>>3, SEEK_SET); size_t len=read(fd, &buf, 1); //if not set yet if (len<=0) buf=0; return (buf>>(pos % 8))&1; } bool readBool(char *buf, uint64 pos) { if (pos<0 || pos>UINT32_MAX) { cout<<"too big or too small"<<endl; return false; } return (buf[pos>>3]>>(pos % 8))&1; } void writeFF(int fd, size_t block_size, size_t count) { char buf[block_size]; memset(buf, 0xFF, sizeof(buf)); lseek(fd, 0, SEEK_SET); for(int i=0;i<count;++i) write(fd, buf, block_size); } void makePT(int fd) { //init writeFF(fd, 4096, UINT32_MAX/8/4096); cout<<"init done"<<endl; writeBool(fd, 0, false); writeBool(fd, 1, false); for(int i=2;i<=UINT32_MAX_SQRT;++i) { if (readBool(fd, i) && ((UINT32_MAX/i)>i) ) { for(int j=i*i;j<=UINT32_MAX;j+=i) { writeBool(fd, j, false); } } } } void loadPT(int fd, char *buf) { size_t readlen=0; lseek(fd, 0, SEEK_SET); while(readlen<UINT32_MAX/8) { int currlen=read(fd, buf+readlen, UINT32_MAX/8); if (currlen<=0) { return; } readlen+=currlen; } cout<<"load done"<<endl; } inline uint64 myclock() { timeval tv; gettimeofday(&tv, NULL); return /*tv.tv_sec*1000000 +*/ tv.tv_usec; } int main() { int fd=open("./pt.bin", O_RDWR | O_CREAT, 0644); char *buf=new char[UINT32_MAX/8]; loadPT(fd, buf); close(fd); uint64 n; uint64 t1, t2, t3; while(cin>>n) { cout<<n<<" is "; t1=myclock(); t2=myclock(); bool isP=readBool(buf, n); t3=myclock(); cout<<(isP?"":"NOT ")<<"a prime."<<endl; cout<<"time usage: "<<(t3-t2-(t2-t1))<<endl; } delete [] buf; return 0; }
哦, 我的老兄, 有的人竟然不知道这是Linux下写出来的, 居然还会有人用VC++来编译它。
哦, 我的天哪。
发表评论