Відмінності між версіями «Тест простоти»

→‎Наївні методи: курсив для змінних, "для" замість "lkz", посилання на статтю "приморіал" (англ.)
м (свідчення -> свідок)
(→‎Наївні методи: курсив для змінних, "для" замість "lkz", посилання на статтю "приморіал" (англ.))
перевірити чи якесь ціле ''m'' від 2 до ''n-1'' [[подільність|ділить]] ''n''. Якщо ''n'' ділиться на певне ''m'', то ''n'' складене, в іншому разі воно просте.
Замість перевірки всіх ''m'' до ''n-1'', досить лише перевірити ''m'' до <math>\sqrt n</math>: якщо ''n'' складене, то його можна розкласти на два множники, принаймні один з яких не перевищує <math>\sqrt n</math>.
Можна також покращити ефективність, пропускаючи всі парні ''m'' , за винятком 2, бо коли якесь парне число ділить ''n'' , то 2 також ділить. Можна далі вдосконалити зауважуючи, що всі прості числа, за винятком 2 та 3, мають вигляд 6k ± 1. Дійсно, всі цілі можна подати як (6k6''k'' + ''i'') для деякого ''k'' та для ''i'' = -1, 0, 1, 2, 3, або 4; 2 ділить (6k6''k'' + 0), (6k6''k'' + 2), (6k6''k'' + 4); а 3 ділить (6k6''k'' + 3). Спочатку перевіряємо чи ''n'' ділиться на 2 або 3, тоді пробігаємо всі числа вигляду 6k6''k'' ± 1<math>\leq</math><math>\sqrt n</math>. Це у 3 рази швидше від попереднього методу. Насправді, всі прості мають вигляд ''c#k + i'' lkzдля ''i<c#'' де ''і'' належить до чисел, [[взаємно прості числа|взаємно простих]] з [[:en:Primorial|c#]] (приморіал) . Фактично, коли <math>c \rightarrow \infty</math> кількість значень, які ''c#k + i'' може набувати в певному діапазоні, зменшується, а, отже, час тестування <math>n </math> зменшується. Для цього методу, слід ділити на всі прості менші ніж ''c''. Спостереження, аналогічні до попереднього, можна застосувати [[рекурсія|рекурсивно]], отримуючи [[решето Ератосфена]].
Вдалим способом пришвидшення цих методів (і всіх інших згаданих далі) є попередній обрахунок і зберігання списку всіх простих до певної межі, скажімо всіх простих до 200. (Такий список можна обчислити за допомогою решета Ератосфена). Тоді, перед тестуванням ''n'' на простоту з використанням серйозного методу, спочатку перевіряємо чи ''n'' не ділиться на якесь просте із цього списку.
 
Анонімний користувач