|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Изучая труды Эратосфена Киренского Вася прочитал о «решете Эратосфена», т.е. необходимо найти все простые числа на отрезке, ограниченном числом N.
Алгоритм, который описан Эратосфеном, Вася захотел запрограммировать.
Например, на отрезке [0;10] простые числа 2; 3; 5; 7.
Формат входных данных
На вход подается одно целое число N (0≤N≤ 720 000 000);
Формат выходных данных
Выведите единственный элемент – количество простых чисел.
|
Ввод 1
|
Ввод 2
|
|
10
|
1 000 000
|
|
Вывод 1
|
Вывод 2
|
|
4
|
78498
|
Для отправки решений необходимо выполнить вход.
|