027.cpp

Go to the documentation of this file.

#include <iostream>
using namespace std;

const unsigned MAX = 1000000;
class prime_table
{
        bool x[MAX];
public:
        prime_table();
        bool has(unsigned k);
        unsigned next(unsigned n);
};

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

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

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

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

unsigned test(prime_table& prime, int a,int b)
{
        unsigned k;
        for (k=0;k< MAX;k++)
                if (!prime.has(k*k+a*k+b))
                        break;
        return (k==0)?0:(k-1);
}

int main(int argc, char **argv)
{
        prime_table prime;
        unsigned max_n = 0;
        int A,B;
        for (int i=-999;i<1000;i++)
                for (int j=-999;j<1000;j++) {
                        unsigned temp = test(prime,i,j);
                        if (temp > max_n) {
                                max_n=temp;
                                A=i;
                                B=j;
                        }
                }
        cout << A*B << endl;
        return 0;
}