Быстрая проверка небольших чисел на простоту на экзамене

[AchilleS]

Приведите пример способа быстрого нахождения простых чисел на определенном отрезке.
Лично я знаю несколько (в основном, все работают по принципу "решета" ), но все они занимают довольно много времени.

[maxal]

Сначала решето, чтобы отсеять числа с маленькими простыми делителями, а затем перебор отставшихся с каким-нибудь быстрым вероятностным тестом простоты типа Миллера-Рабина.

[AchilleS]

Сейчас кое-что почитал про этот тест По-моему, он займет больше времени, чем простое деление всех сомнительных чисел. Конечно, если числа очень большие, то понятно - он полезен, но если числа, ну скажем, трехзначные, то - довольно сложный.

[незваный гость]

А с трех- четырехзначными проще всего проверить в таблице (вбитой в программу).

[AchilleS]

По какой таблице? На экзамене же ничего не будет!

[PAV]

Это на каком, интересно, экзамене, просят найти все простые числа на некотором отрезке?

[AchilleS]

вступительный в ГУ-ВШЭ

[PAV]

И какого типа отрезок (порядок)?

[AchilleS]

задание такое: Сколько простых чисел расположено в промежутке (84; 102)
Понятно: задание несложное при наличии времени, но его как раз-таки и не хватает! Я просто хочу найти такой способ, чтобы не вычислять каждое простое число, а сразу находить их количество.

[PAV]

Ну, это явно методом решета надо делать, даже проще. Выписать все числа из промежутка, можно сразу опускать те, которые явно не простые (сразу виден делитель). Далее, надо использовать простой факт, что если число $x$ имеет делители, то хотя бы один из них не превосходит $\sqrt{x}$. А значит, в данном случае надо проверить только делимость на простые числа до 10.

[Руст]

Здесь подойдет обычный метод решета. Вычеркиваем все чётные, потом делящиеся на три, на пять и на семь. Оставшиеся простые - 83, 89, 97.

[AchilleS]

Это именно для данного случая? Как я понял, то если числа находятся в пределах ста, то корень из ста будет 10, значит остается проверить все числа до 10?

[Руст]

AchilleS писал(а):

Это именно для данного случая? Как я понял, то если числа находятся в пределах ста, то корень из ста будет 10, значит остается проверить все числа до 10?

Проверить на простые меньше 10.

[AchilleS]

Именно. А другого способа нет. В основном остается проверить 7-9 чисел в аналогичных заданиях - это отнимает около 5-7 минут. А там счет идет чуть ли не на секунды.

[Руст]

Когда числа в пределах 100000, лучшего алгоритма нет. Все мудрёные алгоритмы более экономны при проверке больших чисел на простоту. Конечно для специального вида чисел есть алгоритмы апроверки на простоту специально для таких чисел.