041_prime_table.h

Go to the documentation of this file.

#ifndef _INCL_PRIMETABLE
#define _INCL_PRIMETABLE
class prime_table
{
        unsigned prime_max;
        bool* x;
public:
        prime_table(unsigned);
        ~prime_table();
        bool has(unsigned);
        unsigned next(unsigned);
};

prime_table::~prime_table(){
delete[] x;
}

prime_table::prime_table(unsigned prime_max)
{
        this-> prime_max = prime_max;
        x = new bool[prime_max];
        //assume all except 0,1 are prime
        x[0]=x[1]=0;
        for (bool* p=x+2;p-x<prime_max;p++)*p=1;

        for (unsigned n = 2; n < prime_max;n = next(n)) {
                unsigned idx=n+n;
                while (idx < prime_max) {
                        x[idx]=0;
                        idx+=n;
                }
        }
}

unsigned prime_table::next(unsigned n)
{
        if (n>=prime_max)return prime_max;
        bool* p = x+n;
        do {
                p++;
                if (*p)return (p-x);
        } while (p-x < prime_max);
        return prime_max;
}

bool prime_table::has(unsigned k)
{
        return x[k];
}
#endif