#include <iostream>
using namespace std;
int main() {
// your code goes here
int arr[1003003], i, j;
for(int k=0; k<1003003; k++) arr[k]=true;
arr[0]=arr[1]=false;
for(i=2; i*i<=1003003; i++) {
if(!arr[i]) continue; //doesnt execute the inner loop if "i" is
for(j=i*i; j<=1003003; j=j+i) { // false, or not prime
arr[j]=false; //all multiples of "i" are assigned "false", or not prime
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglpbnQgYXJyWzEwMDMwMDNdLCBpLCBqOwkJCQkJCQkKCWZvcihpbnQgaz0wOyBrPDEwMDMwMDM7IGsrKykgYXJyW2tdPXRydWU7CglhcnJbMF09YXJyWzFdPWZhbHNlOwoJZm9yKGk9MjsgaSppPD0xMDAzMDAzOyBpKyspIHsgCQkJCQkKCQlpZighYXJyW2ldKSBjb250aW51ZTsJCQkJCS8vZG9lc250IGV4ZWN1dGUgdGhlIGlubmVyIGxvb3AgaWYgImkiIGlzCgkJZm9yKGo9aSppOyBqPD0xMDAzMDAzOyBqPWoraSkgewkJCS8vIGZhbHNlLCBvciBub3QgcHJpbWUKCQkJYXJyW2pdPWZhbHNlOwkJLy9hbGwgbXVsdGlwbGVzIG9mICJpIiBhcmUgYXNzaWduZWQgImZhbHNlIiwgb3Igbm90IHByaW1lCgkJfQoJfQoJcmV0dXJuIDA7Cn0=