Алгоритм проверки числа на простоту.
Сейчас решаю олимпиадную задачу, застрял на проверке числа на простоту. Если кто знает эффективные алгоритмы напишите плизз. Сам сначала проверяю подходит ли число к формуле 6n+-1 если да, то уже перебираю делители от 2 до половины этого числа(естественно обрываю цикл сразу после нахождения). Составные числа быстро отсеивает, а вот на простых по долгу засиживается. Числа у меня в промежутке от 10000 до 99999. Заранее спасибо.

Kn793, а не проще-ли проверять остаток от деления на 2?

Kosti@n, в смысле ПРОВЕРЯТЬ? На что проверять?

Kn793, на остаток. Если приделении на 2 есть остаток (при условии что число больше числа 2), то число простое

Kosti@n, простое и четное это не одно и тоже.

Kosti@n, с чего ты взял, что число в этом случае простое? Например 9 - остаток есть, но число составное (3*3).

Kn793, эт я знаю

Kosti@n, ты написал алгоритм проверки числа на четность!

cHeRsAnYa1, мда, не усмотрел. Хоть щас вроде речь идёт об у меньшении работы расчёта для несоставных простых чисел. Имеется ввиду 2, 5, 8, 11 и т.д.

Eterhard, читай посты выше.

Kosti@n, простое в смысле то, которое делится на цело только на само себя и единицу.

Подождите минут пять, посмотрю у меня он где то был.