Проблема, как найти все простые числа в диапазоне [n,m]. Посмотрел различные алгоритмы решета, к сожалению, везде начинается перебор с 2. Что мне совсем не подходит.

задан 5 Янв '12 4:17

изменен 5 Янв '12 4:18

Это невозможно,по-моему, уважаемый Артем. Ведь для проверки числа a (n <= a <= m) на простоту необходимо вычислить или знать набор простых чисел, меньших, чем n.

(5 Янв '12 14:11) BuilderC

@BuilderC, достаточно знать лишь простые числа до $%\sqrt{m}$%.

(5 Янв '12 18:15) freopen

@freopen, а теперь я Вас не понял. Артем же не хочет вычислять простые числа вне диапазона. Это невозможно, что и сказано мной. Про корень из m я знаю.

(6 Янв '12 0:35) BuilderC

@BuilderC, ну когда возникает такая задача, обычно, $%\sqrt{m}$% очень сильно меньше, чем $%n$%. Про то, что он не хочет вычислять простые числа, я не очень понял. Из исходного сообщения это не очень то выводится..

(6 Янв '12 1:30) freopen
10|600 символов нужно символов осталось
2

Очевидно, что если число составное, то оно имеет делитель не больший, чем $%\sqrt{m}$%. Найдем все такие простые числа (например, с помощью решета до корня) и просеем ими диапазон. Подробнее можно почитать тут.

ссылка

отвечен 5 Янв '12 7:37

изменен 5 Янв '12 20:01

Спасибо, господин freopen. Статья оказалась очень полезной.

(6 Янв '12 0:11) Artem Gorev
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×173
×14

задан
5 Янв '12 4:17

показан
2121 раз

обновлен
6 Янв '12 1:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru