Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Постулат Бертрана

(Время: 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.TXTOUTPUT.TXT
121
223939
33000353

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки] [Решение]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483