|
| Комментарии | | #1 Автор: nil (2013.08.14 14:17) | | Тест числа на простоту весьма не тривиальная задача. Известно что наименьший делитель числа не превосходит квадратного корня из него. |
| #2 Автор: Nika (2013.08.15 22:10, изменений: 2, 2013.08.15 23:19) | nil,
тест числа на "простоту" - это на самом деле элементарно:
BOOL is_simple(int num);
{
int div=1;
while (div++<num-1)
if(num/div*div==num) return(FALSE);
return(TRUE);
}
Естественно, элементарно с применением ЭВМ.
В этом случае прекрасно подходят подобные "тупые" методы. |
| #3 Автор: SergeCpp (2013.08.16 02:45) | У Кнута (том 2, раздел 4.5.4) достаточно подробно рассматриваются разные способы проверки.
Простейший же способ можно ускорить, деля на 2, 3, 5, 7, 11, 13, 17, 19, 23... пока частное остаётся больше делителя. Последовательность взята у Кнута, её члены, кроме первых трёх, получаются посредством попеременного увеличения предыдущих на 2 и 4.
|
| #4 Автор: Nika (2013.08.16 03:03, изменений: 1, 2013.08.16 03:13) | SergeCpp,
да, я помню о Кнуте, у него там очень хорошо всё это расписано.
Но зато здесь, при dumb-методе, алгоритм, понятный и ребёнку.
И всего три строчки (которые можно свернуть вообще в одну).
|
| |
|
Английский![[Не подделка]](http://old-dos.ru/img/nofake.png){kind=small}
