Wandai Blog 共被围观 1,584,337 次

生成好了质数表, 这里可以下载(解压后的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++来编译它。

哦, 我的天哪。