Алгоритм проверки числа на простоту. | SEclub.org
Алгоритм проверки числа на простоту.
Все новые
Всего сообщений: 38
*
Kn793
12 май 2008 в 17:37
Алгоритм проверки числа на простоту.
Сейчас решаю олимпиадную задачу, застрял на проверке числа на простоту. Если кто знает эффективные алгоритмы напишите плизз. Сам сначала проверяю подходит ли число к формуле 6n+-1 если да, то уже перебираю делители от 2 до половины этого числа(естественно обрываю цикл сразу после нахождения). Составные числа быстро отсеивает, а вот на простых по долгу засиживается. Числа у меня в промежутке от 10000 до 99999. Заранее спасибо.
*
Kostian90
12 май 2008 в 17:48
Kn793, а не проще-ли проверять остаток от деления на 2?
*
Kn793
12 май 2008 в 18:34
Kosti@n, в смысле ПРОВЕРЯТЬ? На что проверять?
*
Kostian90
12 май 2008 в 18:48
Kn793, на остаток. Если приделении на 2 есть остаток (при условии что число больше числа 2), то число простое
*
Kn793
12 май 2008 в 19:13
Kosti@n, простое и четное это не одно и тоже.
*
cHeRsAnYa1
12 май 2008 в 19:13
Kosti@n, с чего ты взял, что число в этом случае простое? Например 9 - остаток есть, но число составное (3*3).
*
Kostian90
12 май 2008 в 19:15
Kn793, эт я знаю
*
Eterhard
12 май 2008 в 19:15
Kosti@n, ты написал алгоритм проверки числа на четность! :)
*
Kostian90
12 май 2008 в 19:17
cHeRsAnYa1, мда, не усмотрел. Хоть щас вроде речь идёт об у меньшении работы расчёта для несоставных простых чисел. Имеется ввиду 2, 5, 8, 11 и т.д.
*
Kostian90
12 май 2008 в 19:18
Eterhard, читай посты выше.
*
Kn793
12 май 2008 в 19:20
Kosti@n, простое в смысле то, которое делится на цело только на само себя и единицу.
*
Eterhard
12 май 2008 в 19:21
Подождите минут пять, посмотрю у меня он где то был.
Скачать тему
Для полноценного использования разделов сайта войдите или зарегистрируйтесь.
Создание сайтов и программирование | Компьютеры | Форум | Главная
18+ © Seclub.org 2003-2016