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

Перейти до навігації Перейти до пошуку
м
→‎Наївні методи: суміш розкладок
м (Вилучення 19 інтервікі, відтепер доступних на Вікіданих: d:q829546)
м (→‎Наївні методи: суміш розкладок)
перевірити чи якесь ціле ''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. Дійсно, всі цілі можна подати як (6k + i) для деякого k та для i = -1, 0, 1, 2, 3, або 4; 2 ділить (6k + 0), (6k + 2), (6k + 4); а 3 ділить (6k + 3). Спочатку перевіряємо чи n ділиться на 2 або 3, тоді пробігаємо всі числа вигляду 6k ± 1<math>\leq</math><math>\sqrt n</math>. Це у 3 рази швидше від попереднього методу. Насправді, всі прості мають вигляд c#k + i lkz i<c# де iі належить до чисел, [[взаємно прості числа|взаємно простих]] з c#. Фактично, коли <math>c \rightarrow \infty</math> кількість значень, які c#k + i може набувати в певному діапазоні, зменшується, а, отже, час тестування <math>n </math> зменшується. Для цього методу, слід ділити на всі прості менші ніж c. Спостереження, аналогічні до попереднього, можна застосувати [[рекурсія|рекурсивно]], отримуючи [[решето Ератосфена]].
Вдалим способом пришвидшення цих методів (і всіх інших згаданих далі) є попередній обрахунок і зберігання списку всіх простих до певної межі, скажімо всіх простих до 200. (Такий список можна обчислити за допомогою решета Ератосфена). Тоді, перед тестуванням ''n'' на простоту з використанням серйозного методу, спочатку перевіряємо чи ''n'' не ділиться на якесь просте із цього списку.
 
238 646

редагувань

Навігаційне меню