Поиск

Решето Эратосфена


Ограничение времени - 1 секунда

Ввод - input.txt

Ограничение памяти - 16Mb

Вывод - output.txt

Пусть мы хотим найти все простые числа до 100. Выпишем числа от 2 до 100, затем первое число (2) оставим, а все остальные делящиеся на 2 числа вычеркнем. Затем оставим первое невычеркнутое число, отличное от 2, это 3, а все остальные еще невычеркнутые и делящиеся на 3 вычеркнем. Затем опять оставим первое невычеркнутое число, отличное от 2 и 3, это 5, а все остальные еще невычеркнутые и делящиеся на 5 вычеркнем. И так далее. В итоге останутся невычеркнутыми только простые числа до 100. Какое число будет вычеркнуто последним, если мы ищем простые числа до заданного n? Считаем, что каждое число может быть вычеркнуто ровно один раз. То есть, если 30 вычеркнули как делящееся на 2, то вычеркнуть его же как делящееся на 3 мы уже не можем. Например, если искать все простые числа от 2 до 10, то последним будет вычеркнуто число 9.


Формат ввода

В единственной строке входного файла INPUT.TXT записано натуральное число n (4 ≤ n ≤ 109).


Формат вывода

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно число – последнее вычеркнутое число.

Пример

Ввод

10

Вывод

9

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