namespace HomeAlone
{
internal class Program
{
static void Main(string[] args)
{
int n = 5000000;
int cnt = 0;
bool[] primes = new bool[n + 1];
for (int i = 2; i < n; i++)
{
if (primes[i] == true) continue;
else
{
cnt++;
int temp = i + i;
while (temp < n)
{
primes[temp] = true;
temp += i;
}
}
}
Console.WriteLine(cnt);
}
}
}
bmFtZXNwYWNlIEhvbWVBbG9uZQp7CiAgICBpbnRlcm5hbCBjbGFzcyBQcm9ncmFtCiAgICB7CiAgICAgICAgc3RhdGljIHZvaWQgTWFpbihzdHJpbmdbXSBhcmdzKQogICAgICAgIHsKICAgICAgICAgICAgaW50IG4gPSA1MDAwMDAwOwogICAgICAgICAgICBpbnQgY250ID0gMDsKICAgICAgICAgICAgYm9vbFtdIHByaW1lcyA9IG5ldyBib29sW24gKyAxXTsKCiAgICAgICAgICAgIGZvciAoaW50IGkgPSAyOyBpIDwgbjsgaSsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZiAocHJpbWVzW2ldID09IHRydWUpIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGNudCsrOwogICAgICAgICAgICAgICAgICAgIGludCB0ZW1wID0gaSArIGk7CiAgICAgICAgICAgICAgICAgICAgd2hpbGUgKHRlbXAgPCBuKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgcHJpbWVzW3RlbXBdID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgdGVtcCArPSBpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZShjbnQpOwogICAgICAgIH0KICAgIH0KfQo=