Зміст

• Крок
• Спосіб 1 з 4: Спробуйте розділити
• Метод 2 з 4: Використання Малої теореми Ферма
• Метод 3 з 4: Використання тесту Міллера-Рабіна
• Метод 4 з 4: Використання китайської теореми про залишки
• Поради
• Потреби

Прості числа - це числа, які діляться лише самі на себе і називаються 1 - іншими числами з'єднання числа. Коли йдеться про тестування того, чи є число простим, існує кілька варіантів. Деякі з цих методів відносно прості, але зовсім не практичні для більшої кількості. Інші часто використовувані тести насправді є повними алгоритмами, заснованими на одному ймовірність які іноді помилково вважають число простим. Прочитайте крок 1, щоб дізнатись, як перевірити себе, чи маєте справу з простим числом.

Крок

Спосіб 1 з 4: Спробуйте розділити

Спроба розділити - це найпростіший спосіб перевірити число. Для невеликих чисел це, як правило, також найшвидший спосіб. Тест базується на визначенні простого числа: число є простим, якщо воно ділиться лише на себе і 1.

1. Припустимо n - це число, яке потрібно перевірити. Поділіть число n на всі можливі цілі числа, що діляться. Для більших чисел, таких як n = 101, надзвичайно недоцільно ділити на будь-яке можливе ціле число менше n. На щастя, існує декілька хитрощів для зменшення кількості факторів, що перевіряються.
2. Визначте, чи n навіть. Усі парні числа повністю діляться на 2. Отже, якщо n парне, ви можете це сказати n - складене число (і, отже, не просте число). Щоб швидко визначити, чи число є парним, потрібно лише звернути увагу на останню цифру. Якщо останньою цифрою є 2, 4, 6, 8 або 0, то число є парним і не простим.
   • Єдиним винятком із цього правила є саме число 2, яке, оскільки воно ділиться саме на себе та 1, також є простим. 2 є єдиним парним простим.
3. Частина n на будь-яке число від 2 до n-1. Оскільки просте число не має інших факторів, крім нього самого і 1, і оскільки цілі множники менші за їх добуток, перевірка подільності цілого числа менше n і більше 2 визначатиме, чи n є простим. Ми починаємо після 2, оскільки парні числа (кратні 2) не можуть бути простими числами. Як ви побачите нижче, це далеко не ефективний спосіб тестування.
   • Наприклад, якби ми хотіли використовувати цей метод, щоб перевірити, чи є 11 простим чи ні, ми б розділили 11 на 3, 4, 5, 6, 7, 8, 9 і 10, шукаючи цілочисельну відповідь без залишку. Оскільки жодне з цих чисел повністю не вкладається в 11, ми можемо сказати, що 11 - це одне є головним.
4. Щоб заощадити час, протестуйте лише до sqrt (n), заокруглений. Тестування числа n шляхом перевірки всіх чисел від 2 до n-1 може швидко зайняти багато часу. Наприклад, якби ми хотіли перевірити, чи 103 є простим за допомогою цього методу, нам довелося б розділити на 3, 4, 5, 6, 7 ... тощо, аж до 102! На щастя, тестувати подібним чином не потрібно. На практиці необхідно лише перевірити коефіцієнти від 2 до квадратного кореня з n. Якщо квадратний корінь з n не є числом, округляйте його до найближчого цілого числа і перевіряйте на це число. Пояснення див. Нижче:
   • Давайте вивчимо фактори 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 і 100 × 1. Зверніть увагу, що після 10 × 10 фактори збігаються якщо це для 10 × 10, лише тоді перевернуто. Загалом, ми можемо ігнорувати фактори n, більші за sqrt (n), оскільки вони є просто продовженням факторів, менших за sqrt (n).
   • Давайте спробуємо приклад. Якщо n = 37, то нам не потрібно перевіряти всі числа від 3 до 36, щоб визначити, чи n є простим. Натомість нам просто потрібно поглянути на цифри від 2 до sqrt (37) (округлено).
     • sqrt (37) = 6,08 - ми округлимо це до 7.
     • 37 не цілком ділиться на 3, 4, 5, 6 і 7, і тому ми можемо впевнено стверджувати, що він один просте число є.
5. Щоб заощадити ще більше часу, ми використовуємо лише прості множники. Можна зробити процес тестування діленням ще коротшим, не враховуючи тих факторів, які не є простими числами. За визначенням, кожне складене число можна виразити як добуток двох або більше простих чисел. Тож ділити число n на складене число непотрібно - це еквівалентно діленню на прості числа кілька разів. Отже, ми можемо ще більше звузити перелік можливих факторів лише до простих чисел, менших за sqrt (n).
   • Це означає, що всі парні множники, а також множники, кратні простим числам, можна пропустити.
   • Наприклад, спробуємо визначити, чи є 103 простим чи ні. Квадратний корінь із 103 дорівнює 11 (округлено вгору). Прості числа від 2 до 11 - це 3, 5, 7 і 11. 4, 6, 8 і 10 є парними, а 9 - кратне 3, просте число, тому ми можемо його пропустити. Роблячи це, ми скоротили наш перелік можливих факторів лише до 4 цифр!
     • 103 не повністю ділиться ні на 3, 5, 7, ні на 11, тож тепер ми знаємо, що 103 - це одне просте число є.

Метод 2 з 4: Використання Малої теореми Ферма

У 1640 р. Французький математик П'єр де Ферма вперше запропонував теорему (нині названу на його честь), яка може бути дуже корисною для визначення того, чи є число простим чи ні. Технічно тест Ферма призначений для перевірки того, що число є складеним, а не простим. Це пояснюється тим, що тест може показати з "абсолютною впевненістю", що число є складеним, але лише "ймовірність" того, що число є простим. Маленька теорема Ферма корисна в ситуаціях, коли спроба розділити недоцільна і коли є список чисел, які є винятками з теореми.

1. Припустимо n номер призначений для тестування. Ви використовуєте цей тест, щоб визначити, чи дане число n є простим. Однак, як зазначалося вище, ця теорема може іноді помилково характеризувати деякі сполуки як прості. Важливо врахувати це та перевірити свою відповідь, яка пояснюється нижче.
2. Виберіть ціле число a від 2 до n-1 (включно). Точне ціле число, яке ви вибрали, не важливо. Оскільки параметри для a включають 2 і n-1, ви також можете їх використовувати.
   • Приклад: 100 основних чи ні. Припустимо, візьмемо 3 як тестове значення - це від 2 до n-1, тож цього достатньо.
3. обчислити a (мод n). Для опрацювання цього виразу потрібні певні знання математичної системи, яка називається модульна математика. У модульній математиці числа повертаються до нуля при досягненні певного значення, також відомого як модуль. Ви можете думати про це як про годинник: з часом стрілка годинника повернеться до 1 години після 12 години, а не до 13 години. Модуль позначається як (mod n). Отже, на цьому кроці ви обчислюєте a з модулем n.
   • Інший метод - обчислити a, потім розділити його на n, а потім використати залишок як свою відповідь. Спеціалізовані калькулятори з модульною функцією можуть бути дуже корисними при діленні великих чисел, оскільки вони можуть негайно обчислити залишок від ділення.
   • Використовуючи такий калькулятор у нашому прикладі, ми можемо побачити, що 3/100 має залишок 1. Отже, 3 (mod 100) є 1.
4. Якщо ми обчислюємо це вручну, ми використовуємо показник ступеня як короткий формат. Якщо у вас немає калькулятора з функцією модуля, використовуйте позначення з показником ступеня, щоб полегшити процедуру визначення залишку. Дивись нижче:
   • У нашому прикладі ми обчислюємо 3 з модулем 100. 3 - це дуже, дуже велике число - 515 377 520 732 031 331 036 461 129 765 621 272 702 1057 522 001 - настільки велике, що з ним стає дуже важко працювати. Замість того, щоб використовувати 48-значну відповідь для 3, нам краще записати її як показник ступеня, тому (((((((3)*3))))*3)). Пам’ятайте, що взяття показника ступеня має ефект множення показників ((x) = x).
     • Тепер ми можемо визначити решту. Почніть з розв’язування (((((((3) * 3))))) * * 3)) у внутрішньому наборі дужок і пройдіть вихід, розділивши кожен крок на 100. Як тільки ми знайдемо решту, ми використаємо це для наступного кроку, а не фактичну відповідь. Дивись нижче:
       • (((((((9) * 3)))) * 3)) - 9/100 не має залишку, тому ми можемо продовжувати.
       • ((((((27)))) * 3)) - 27/100 не має залишку, тому ми можемо рухатися далі.
       • (((((729))) * 3)) - 729/100 = 7 R 29. Наш залишок - 29. Ми продовжуємо наступний крок, а не 729.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. На наступному кроці ми знову використовуємо нашу залишок 41.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Ми використовуємо наш залишок 81 на наступному кроці.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Ми використаємо наш залишок 43 на наступному кроці.
       • (43 = 1849) - 1849/100 = 18 R 49. Ми використаємо наш решту 49 на наступному кроці.
       • 49 = 2401 - 2401/100 = 24 R 1. наш остаточний залишок дорівнює 1. Іншими словами, 3 (mod 100) = 1. Зверніть увагу, що це та сама відповідь, яку ми розрахували на попередньому кроці!
5. Дізнайтеся, чи a (мод n) = a (мод n). Якщо ні, то n - складений. Якщо вірно, то n можливо, (але не впевнений) просте число. Повторення тесту з різними значеннями для може зробити результат більш певним, але є рідкісні складені числа, які задовольняють теорему Ферма для всі значення а. Вони називаються числами Кармайкла - найменше з них - 561.
   • У нашому прикладі 3 (mod 100) = 1 і 3 (mod 100) = 3,1 ≠ 3, тому можна сказати, що 100 - це складене число.
6. Використовуйте цифри Кармайкла, щоб бути впевненими у своєму результаті. Знання, які цифри відповідають серії Кармайкла, перш ніж продовжувати, може заощадити вам багато турбот щодо того, чи є число простим чи ні. Загалом, числа Кармайкла є добутком окремих простих чисел, де для всіх простих чисел воно вважає, що якщо p є дільником n, то p-1 також є дільником n-1. Онлайн-список чисел Кармайкла може бути дуже корисним для визначення того, чи є число простим, використовуючи Малу теорему Ферма.
   
   

Метод 3 з 4: Використання тесту Міллера-Рабіна

Тест Міллера-Рабіна працює так само, як мала теорема Ферма, але краще працює з нестандартними числами, такими як числа Кармайкла.

1. Припустимо n - непарне число, яке ми хочемо перевірити на первинність. Як і у вищезазначених методах, n є змінною, для якої ми хочемо визначити первинність.
2. Тиск n-1 у вигляді 2 × d при якій d непарна. Число n є простим, якщо воно непарне. Отже, n - 1 має бути парним. Оскільки n - 1 парне, його можна записати у степінь, що вдвічі перевищує непарне число. Отже, 4 = 2 × 1; 80 = 2 × 5; і так далі.
   • Припустимо, ми хочемо визначити, чи n = 321 є простим. 321 - 1 = 320, що ми можемо виразити як 2 × 5.
     • У цьому випадку n = 321 - відповідне число. Визначення n - 1 для n = 371 може вимагати великого значення для d, ускладнюючи весь процес на пізньому етапі. 371 - 1 = 370 = 2 × 185
3. Виберіть будь-яке число a від 2 до n-1. Точне число, яке ви вибрали, не має значення - просто воно повинно бути менше n і більше 1.
   • У нашому прикладі з n = 321 ми вибираємо a = 100.
4. обчислити a (мод n). Якщо a = 1 або -1 (мод n), потім проходить n тест Міллера-Рабіна і є ймовірно просте число. Як і у випадку з Малою теоремою Ферма, цей тест не може визначити з абсолютною достовірністю первинність числа, але вимагає додаткових тестів.
   • У нашому прикладі з n = 321, a (mod n) = 100 (mod 321). 100 = 10 000 000 000 (мод 321) = 313. Ми використовуємо спеціальний калькулятор або скорочений метод із показником ступеня, як описано раніше, щоб знайти залишок 100/321.
     • Оскільки ми не отримали 1 або -1, ми не можемо з упевненістю сказати, що n є простим. Але нам ще потрібно зробити більше - читайте далі.
5. Оскільки результат не дорівнює 1 або -1, обчисліть a, a, ... і так далі, аж до ad. Обчислити піднятий до степеня d разів, до 2. Якщо будь-який із цих значень дорівнює 1 або -1 (мод n), потім проходить n тести Міллера-Рабіна і, мабуть, є головним. Якщо ви визначили, що n проходить тест, перевірте свою відповідь (див. Крок нижче). Якщо n не проходить будь-який з цих тестів, це один складений номер.
   • Нагадаємо, у нашому прикладі значення а дорівнює 100, значення s дорівнює 6, а d дорівнює 5. Ми продовжуємо тестування, як показано нижче:
     • 100 = 1 × 10.
       • 1 × 10 (мод 321) = 64,64 ≠’ 1 або -1. Продовжуйте йти спокійно.
     • 100 = 1 × 10.
       • 1 × 10 (мод 321) = 244,244 ≠ 1 або -1.
     • На цьому ми можемо зупинитися. s - 1 = 6 - 1 = 5. Зараз ми досягли 4d = 2, і немає потужностей в 2 рази d нижче 5d. Оскільки жодне з наших розрахунків не відповідало 1 або -1, ми можемо сказати, що n = 321 складений номер є.
6. Якщо n проходить тест Міллера-Рабіна, повторіть для інших значень a. Якщо ви виявили, що значення n може бути простим, спробуйте ще раз із іншим випадковим значенням для підтвердження результату тесту. Якщо n насправді просто, це буде вірно для будь-якого значення a. Якщо n - складене число, воно не вдасться на три чверті значень a. Це дає вам більшу впевненість, ніж мала теорема Ферма, де певні складені числа (числа Кармайкла) проходять тест на будь-яке значення a.

Метод 4 з 4: Використання китайської теореми про залишки

1. Виберіть два числа. Одне з чисел не є простим, а друге - число, яке перевіряється на первинність.
   • "Номер тесту1" = 35
   • Номер тесту2 = 97
2. Виберіть дві точки даних, що перевищують нуль і менше TestNumber1 та TestNumber2, відповідно. Вони не можуть бути рівними між собою.
   • Дані1 = 1
   • Дані2 = 2
3. Обчисліть MMI (Математичний мультиплікативний зворотний) для тесту No1 та номера тесту2
   • Обчисліть MMI
     • MMI1 = Тестовий номер2 ^ -1 Мод Тестовий номер1
     • MMI2 = Тестовий номер1 ^ -1 Мод Тестовий номер2
   • Тільки для простих чисел (результат буде для непростих чисел, але це не MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (Номер тесту1 ^ (Номер тесту-2))% Номер тесту2
   • Так:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Створіть двійкову таблицю для кожного MMI аж до Log2 модуля
   • Для MMI1
     • F (1) = Номер тесту 2% Номер тесту1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Номер тесту 1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Номер тесту 1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Номер тесту1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Номер тесту1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Номер тесту1 = 1 * 1% 35 = 1
   • Обчисліть двійковий логарифм TestNumber1 - 2
     • 35 -2 = 33 (10001) база 2
     • MMI1 = F (33) = F (32) * F (1) мод 35
     • MMI1 = F (33) = 1 * 27 Мод 35
     • MMI1 = 27
   • Для MMI2
     • F (1) = Номер тесту1% Номер тесту2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Номер тесту 2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Номер тесту 2 = 61 * 61 мод 97 = 35
     • F (8) = F (4) * F (4)% Номер тесту 2 = 35 * 35 мод 97 = 61
     • F (16) = F (8) * F (8)% Номер тесту 2 = 61 * 61 мод 97 = 35
     • F (32) = F (16) * F (16)% Номер тесту 2 = 35 * 35 мод 97 = 61
     • F (64) = F (32) * F (32)% Номер тесту 2 = 61 * 61 мод 97 = 35
     • F (128) = F (64) * F (64)% Номер тесту 2 = 35 * 35 мод 97 = 61
   • Обчисліть двійковий логарифм TestNumber2 - 2
     • 97 - 2 = 95 = (1011111) основа 2
     • MMI2 = ((((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = ((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. Обчислити (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Відповідь = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Відповідь = (2619 + 4270)% 3395
   • Відповідь = 99
6. Переконайтеся, що "TestNumber1" не є простим1
   • Обчислити (відповідь - дані1)% номер тесту1
   • 99 -1 % 35 = 28
   • Оскільки 28 більше 0, 35 не є простим
7. Перевірте, чи є TestNumber2 простим
   • Обчислити (відповідь - дані2)% номер тесту2
   • 99 - 2 % 97 = 0
   • Оскільки 0 дорівнює 0, 97 є потенційним простим числом
8. Повторіть кроки від 1 до 7 принаймні ще два рази.
   • Якщо крок 7 дорівнює 0:
     • Використовуйте інший "TestNumber1", якщо TestNumber1 не є простим.
     • Використовуйте інший TestNumber1, де TestNumber1 насправді є простим. У цьому випадку кроки 6 і 7 дорівнюють 0.
     • Використовуйте різні точки даних для даних1 та даних2.
   • Якщо крок 7 завжди дорівнює 0, то ймовірність того, що число 2 є простим числом, дуже велика.
   • Кроки з 1 по 7, як відомо, є неправильними в певних випадках, коли перше число не є простим, а друге - простим множником непростого числа "Тестове число1". Це працює у всіх сценаріях, коли обидва числа є простими.
   • Причиною повторення кроків з 1 по 7 є те, що існує кілька сценаріїв, коли навіть якщо TestNumber1 не є простим, а TestNumber2 не є простим, будь-яке число з кроку 7 все ще дорівнює нулю. Ці стани рідкісні. Змінюючи TestNumber1 на інше непросте число, якщо TestNumber2 не є простим, TestNumber2 більше не буде дорівнювати нулю на кроці 7. За винятком випадку, коли "TestNumber1" є коефіцієнтом TestNumber2, прості числа завжди будуть нульовими. крок 7.

Поради

• 168 простих чисел під 1000: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
• Коли спроба ділити відбувається повільніше, ніж складніші методи, вона все одно ефективна для менших чисел. Навіть під час тестування більших чисел, нерідкі випадки, коли спочатку перевіряють малі цифри, перш ніж переходити на більш просунуті методи.

Потреби

• Папір, ручка, олівець та / або калькулятор для розробки