Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого \(n > 1\) найдется простое число p в интервале \(n < p < 2n\). Такая гипотеза была выдвинута в 1845 году французским математиком Джозефом Бертраном (проверившим ее до \(n=3000000\)) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.
Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала \(n < p < 2n\).
Напомним, что число называется простым, если оно делится только само на себя и на единицу
Входные данные
Целое число n (\(2 <= n <= 50000\)).
Выходные данные
Выведите одно число – ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3000 |
353 |