class Prime{
    public int num;
    public boolean[] primeData;
    public boolean[] primeDataSolved;
 
    public Prime(int n){
        num=n;
        initialize();
        solve();
        for (int i=-8;i<=8;i++)
            System.out.println("isPrime("+(num/2+i)+") -> "+isPrime(num/2+i));
    }
 
    public static void main(String[] args){
        new Prime(1000100);
    }
 
    public void initialize(){
        primeData = new boolean[num];       // 全てfalse
        primeDataSolved = new boolean[num]; // 全てfalse
        primeData[0]=false; // ?
        primeData[1]=false;
        primeData[2]=true;
 
    }
 
    public void solve(){
        for (int i=3;i<num;i++){
            int j;
            if (primeDataSolved[i]==true) continue;
            primeDataSolved[i]=true;
            for (j=2;j*j<i;j++)
                if (i%j==0) break;
            if (i%j!=0){
                primeData[i]=true;
                for (j=1;j*i<num;j++)
                    primeDataSolved[j*i]=true;
            }
        }
    }
 
    public boolean isPrime(int i){
        if (i<0 || num<=i) return false;
        return primeData[i];
    }
 
}

CmNsYXNzIFByaW1lewogICAgcHVibGljIGludCBudW07CiAgICBwdWJsaWMgYm9vbGVhbltdIHByaW1lRGF0YTsKICAgIHB1YmxpYyBib29sZWFuW10gcHJpbWVEYXRhU29sdmVkOwogICAgCiAgICBwdWJsaWMgUHJpbWUoaW50IG4pewogICAgICAgIG51bT1uOwogICAgICAgIGluaXRpYWxpemUoKTsKICAgICAgICBzb2x2ZSgpOwogICAgICAgIGZvciAoaW50IGk9LTg7aTw9ODtpKyspCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiaXNQcmltZSgiKyhudW0vMitpKSsiKSAtPiAiK2lzUHJpbWUobnVtLzIraSkpOwogICAgfQogICAgCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKXsKICAgICAgICBuZXcgUHJpbWUoMTAwMDEwMCk7CiAgICB9CiAgICAKICAgIHB1YmxpYyB2b2lkIGluaXRpYWxpemUoKXsKICAgICAgICBwcmltZURhdGEgPSBuZXcgYm9vbGVhbltudW1dOyAgICAgICAvLyDlhajjgaZmYWxzZQogICAgICAgIHByaW1lRGF0YVNvbHZlZCA9IG5ldyBib29sZWFuW251bV07IC8vIOWFqOOBpmZhbHNlCiAgICAgICAgcHJpbWVEYXRhWzBdPWZhbHNlOyAvLyA/CiAgICAgICAgcHJpbWVEYXRhWzFdPWZhbHNlOwogICAgICAgIHByaW1lRGF0YVsyXT10cnVlOwogICAgICAgIAogICAgfQogICAgCiAgICBwdWJsaWMgdm9pZCBzb2x2ZSgpewogICAgICAgIGZvciAoaW50IGk9MztpPG51bTtpKyspewogICAgICAgICAgICBpbnQgajsKICAgICAgICAgICAgaWYgKHByaW1lRGF0YVNvbHZlZFtpXT09dHJ1ZSkgY29udGludWU7CiAgICAgICAgICAgIHByaW1lRGF0YVNvbHZlZFtpXT10cnVlOwogICAgICAgICAgICBmb3IgKGo9MjtqKmo8aTtqKyspCiAgICAgICAgICAgICAgICBpZiAoaSVqPT0wKSBicmVhazsKICAgICAgICAgICAgaWYgKGklaiE9MCl7CiAgICAgICAgICAgICAgICBwcmltZURhdGFbaV09dHJ1ZTsKICAgICAgICAgICAgICAgIGZvciAoaj0xO2oqaTxudW07aisrKQogICAgICAgICAgICAgICAgICAgIHByaW1lRGF0YVNvbHZlZFtqKmldPXRydWU7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICAKICAgIHB1YmxpYyBib29sZWFuIGlzUHJpbWUoaW50IGkpewogICAgICAgIGlmIChpPDAgfHwgbnVtPD1pKSByZXR1cm4gZmFsc2U7CiAgICAgICAgcmV0dXJuIHByaW1lRGF0YVtpXTsKICAgIH0KICAgIAp9