Задача №111172. Решето Эратосфена
Определите \(N=100000\) и создайте массив [True] * (\(N + 1\)).Заполните его значениями так, чтобы IsPrime[\(i\)] == True, если \(i\) —простое число и IsPrime[\(i\)] == False, если \(i\) — составное.
Для этого сначала заполняем массив True.Затем “вычеркиваем” (то есть помечаем нулями) те элементы,которые делятся на 2, начиная с 4. Затем вычеркиваем те элементы, которые делятся на 3,начиная с 9. Затем вычеркиваем элементы, которые делятся на 5, начиная с 25... И так далее —находим следующее невычеркнутое число \(p\) и вычеркиваем все кратные \(p\) начиная с \(p^2\).
В результате невычернутыми останутся только простые числа. Такая процедура называется“Решето Эратосфена”.
Напишите программу, которая строит решето Эратосфена, потом считывает натуральное число \(n\) и выводит n-е по счету простое число. Гарантируется, что это число не превосходит \(N\).
5
11