|
Проблема, как найти все простые числа в диапазоне [n,m]. Посмотрел различные алгоритмы решета, к сожалению, везде начинается перебор с 2. Что мне совсем не подходит. задан 5 Янв '12 4:17 
Artem Gorev |
|
Очевидно, что если число составное, то оно имеет делитель не больший, чем $%\sqrt{m}$%. Найдем все такие простые числа (например, с помощью решета до корня) и просеем ими диапазон. Подробнее можно почитать тут. отвечен 5 Янв '12 7:37 
freopen Спасибо, господин freopen. Статья оказалась очень полезной.
(6 Янв '12 0:11)
Artem Gorev
|
Это невозможно,по-моему, уважаемый Артем. Ведь для проверки числа a (n <= a <= m) на простоту необходимо вычислить или знать набор простых чисел, меньших, чем n.
@BuilderC, достаточно знать лишь простые числа до $%\sqrt{m}$%.
@freopen, а теперь я Вас не понял. Артем же не хочет вычислять простые числа вне диапазона. Это невозможно, что и сказано мной. Про корень из m я знаю.
@BuilderC, ну когда возникает такая задача, обычно, $%\sqrt{m}$% очень сильно меньше, чем $%n$%. Про то, что он не хочет вычислять простые числа, я не очень понял. Из исходного сообщения это не очень то выводится..