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