Постулат Бертрана
(Время: 1 сек. Память: 16 Мб Сложность: 30%)
Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого n > 1 найдется простое число p в интервале n < p < 2n. Такая гипотеза была выдвинута в 1845 году французским математиком Джозефем Бертраном (проверившим ее до n=3000000) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.
Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала n < p < 2n.
Напомним, что число называется простым, если оно делится только само на себя и на единицу.
Входные данные
Входной файл INPUT.TXT содержит целое число n (2 ≤ n ≤ 50000).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 | 1 |
| 2 | 239 | 39 |
| 3 | 3000 | 353 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
