Сегодня на уроке информатики рассказывали про то, как получать все простые числа, не превосходящие заданного числа, с помощью метода, который называется решето Эратосфена. Метод заключается в следующем: пусть мы хотим найти все простые числа от 2 до 100. Выпишем числа от 2 до 100, затем возьмем первое число (2), его оставим, а все остальные делящиеся на 2 числа вычеркнем. Затем возьмем первое невычеркнутое число, отличное от 2, это 3. Его оставим, а все остальные еще невычеркнутые и делящиеся на 3 вычеркнем. Затем опять возьмем первое невычеркнутое число, отличное от 2 и 3, это 5, его оставим, а все остальные еще невычеркнутые и делящиеся на 5 вычеркнем. И так далее. В итоге останутся невычеркнутыми только простые числа. Игорю этот метод очень понравился и он решил с его помощью найти все простые числа, не превосходящие 954530. Какое число он вычеркнет последним? Считаем, что каждое число может быть вычеркнуто ровно один раз. То есть, если 30 вычеркнули как делящееся на 2, то вычеркнуть его же как делящееся на 3 мы уже не можем.