Як перевірити, чи є число простим

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

Кроки

Метод 1 з 4: Перебір дільників

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

1. 

   1

   Нехай n - проверяемое число. Відповідно до цього методу ви повинні розділити число n на всі можливі цілі дільники. При великих значеннях n, наприклад, n = 101, перевірка кожного дільника займе багато часу. Але існують способи зменшити кількість дільників, які потрібно перевірити.

2. 

   2

   Визначте, чи є число n парних. Будь-яке парне число ділиться на 2. Якщо число n - парне, то можна відразу заявити, що воно не є простим (тобто є складовим числом). Для швидкого визначення парності числа зверніть увагу на його останню цифру. Якщо остання цифра 2, 4, 6, 8,0, то число є парним і не є простим.
   • Єдиний виняток з цього правила - число 2. Так як воно ділиться без остачі тільки на себе і на 1, то число 2 - просте число. Таким чином, число 2 є єдиним парних простим числом.

3. 

   3

   Розділіть n на кожне число від 2 до n-1. Так як дільник менше діленого, то перевірка всіх дільників менших n і великих 2 повинна показати, чи є n простим числом. Ви починаєте з числа більшого 2, тому що парні числа (які кратні 2) не є простими числами. Це далеко не найефективніший спосіб тестування чисел на простоту, але тут існує кілька методів оптимізації перевірки.
   • Наприклад, перевіримо число 11. У цьому випадку розділимо (без остачі) 11 на 3, 4, 5, 6, 7, 8, 9, 10. Так як жодне з цих чисел не ділить (без остачі) 11, то число 11 - просте число.

4. 

   4

   Щоб заощадити час, перевірте подільники до округленого значення квадратного кореня (n). Перевірка всіх дільників від 2 до n-1 може зайняти багато часу. Наприклад, якщо ви хочете перевірити число 103, то вам доведеться протестувати наступні подільники: 3, 4, 5, 6, 7 ... і так далі аж до 102! Але цього можна уникнути - перевірте тільки подільники від 2 до округленого значення квадратного кореня (n).
   • Пояснення цього принципу. Розглянемо множники 100. 100 = 1? 100, 2? 50, 4? 25, 5? 20, 10? 10, 20? 5, 25? 4, 50? 2, 100? 1. Зверніть увагу, що після пари множників 10? 10 всі пари множників повторюються (тільки множники в цих парах переставлені місцями). Тому ви можете ігнорувати подільники числа n більші, ніж квадратний корінь (n).
   • Наприклад, перевіримо n = 37. Не потрібно тестувати всі подільники від 3 до 36. Замість цього перевірте подільники між 2 і округленим значенням квадратного кореня (37).
     • Квадратний корінь (37) = 6,08. Округліть це число до 7.
     • 37 не ділиться на 3, 4, 5, 6, 7, тому воно - просте.

5. 

   5

   Для подальшої економії часу тестируйте тільки прості дільники. За визначенням будь складене число може бути виражене як добуток двох або більше простих чисел. Тому поділ числа n на складовою дільник - зайва операція, що повторює багаторазове розподіл числа n на прості дільники. Таким чином, ви можете ще більше звузити тестований ряд дільників.
   • Це означає, що всі парні подільники та все подільники, кратні простим числам, можуть бути опущені.
   • Наприклад, перевіримо число 103. Квадратний корінь з 103 округлюється до 11. Прості подільники від 2 до 11 це 3, 5, 7, 11. Подільники 4, 6, 8, 9, 10 можна опустити (9 кратно 3, а всі інші подільники - парні числа). Таким чином, ви зменшили ряд тестованих дільників до чотирьох чисел.
     • Подільники 3, 5, 7, 11 не ділять (без остачі) число 103, тому воно - просте.

Метод 2 з 4: Тест Ферма

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

1. 

   1

   Нехай n - проверяемое число. Як зазначалося вище, іноді тест ложно ідентифікує складені числа як прості. Тому необхідно перевірити відповідь (спосіб перевірки відповіді описаний нижче).

2. 

   2

   Виберіть будь-яке ціле число «а» від 2 до n-1 (включно).
   • Наприклад, перевіримо на простоту число 100. Припустимо, а = 3.

3. 

   3

   Обчисліть a (Mod n). Обчислення цього виразу зажадає деяких знань з модульної арифметики. В модульної арифметики при досягненні певного значення, званого модулем, відлік чисел починається з нуля. Уявіть це як годинник: годину після полудня - це 1:00, а не 13:00, тобто час після полудня відлічується з нуля. Модуль позначається як mod n. Таким чином, обчисліть a (mod n).
   • Одним із способів обчислення буде обчислити a, а потім розділити результат на n, а в якості відповіді записати залишок поділу. У цьому випадку рекомендується використовувати спеціалізовані калькулятори з функцією модуля, так як вони миттєво обчислюють залишок при діленні великих чисел.
   • У нашому прикладі, при діленні 3/100 виходить залишок 1. Таким чином, 3 (mod 100) = 1.

4. 

   4

   Якщо у вас немає спеціалізованого калькулятора, при обчисленні залишку вручну використовуйте експонентну запис числа.
   • У нашому прикладі вручну обчисліть 3 (mod 100). 3 = 515377520732011331036461129765621272702107522001 - величезне число, з яким важко працювати. Замість того, щоб працювати з 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 (ост.29). Залишок 29. Продовжіть обчислення з числом 29.
       • ((((29 =841)) * 3)) - 841/100 = 8 (ост.41). Залишок 41. Продовжіть обчислення з числом 41.
       • (((41 = 1681) * 3)) - 1681/100 = 16 (ост.81). Залишок 81. Продовжіть обчислення з числом 81.
       • ((81 * 3 = 243)) - 243/100 = 2 (ост. 43). Залишок 43. Продовжіть обчислення з числом 43.
       • (43 = 1849) - 1849/100 = 18 (ост.49). Залишок 49. Продовжіть обчислення з числом 49.
       • 49 = 2401 - 2401/100 = 24 (ост.1). Кінцевий залишок 1. Таким чином, 3 (mod 100) = 1 (такий же результат був отриманий при обчисленні на калькуляторі).

5. 

   5

   Перевірте рівність: a (Mod n) = a (Mod n). Якщо воно не дотримано, то n - складене число. Якщо воно дотримано, то n, швидше за все, просте число (але не обов`язково). Повторіть тест з різними значеннями «а», щоб упевнитися в правильності відповіді. Але є складені числа, що задовольняють умові Ферма при будь-яких значеннях «а». Вони називаються числами Кармайкла (найменше з них - число 561).
   • У нашому прикладі 3 (mod 100) = 1, а 100 (mod 100) = 0. Таким чином, 1? 0 і 100 - складене число.

6. 

   6

   Використовуйте числа Кармайкла в якості гарантії правильності відповіді. Числа Кармайкла мають вигляд (6k + 1) (12k + 1) (18k + 1) для цілих значень k, коли кожен дільник є простим. Ви можете знайти повний список чисел Кармайкла в інтернеті.

Метод 3 з 4: Тест Міллера-Рабіна

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

1. 

   1

   Нехай n - непарне число, яке потрібно протестувати на простоту.

2. 

   2

   Запишіть n-1 у вигляді 2? d, де d - непарне число. Якщо n - просте, то воно має бути непарною. Тому n-1 - парне. Так як n-1 - парне число, то воно може бути представлено у вигляді твору числа 2 в деякій мірі на непарне число. Наприклад, 4 = 2? 1, 80 = 2? 5 і так далі.
   • Наприклад, визначте простоту числа n = 321. 321 - 1 = 320, а 320 = 2? 5. Тобто s = 6 і d = 5.
     • Наприклад, візьмемо більш складне число n = 371. 371 - 1 = 370, а 370 = 2? 185. Тобто d = 185, що значно ускладнить обчислення.

3. 

   3

   Візьміть будь-яке число «а» між 2 і n-1.
   • У нашому прикладі для n = 321 виберіть а = 100.

4. 

   4

   Обчисліть a (Mod n). Якщо a = 1 або -1 (mod n), То число n проходить тест Міллера-Рабіна і, швидше за все, є простим. Однак цей тест, як і тест Ферма, не може визначити простоту числа з абсолютною впевненістю.
   • У нашому прикладі для n = 321: a (mod n) = 100 (mod 321). 100 = 10,000,000,000 (mod 321) = 313. Для знаходження залишку 100/321 використовуйте спеціалізований калькулятор або розрахунок вручну (описаний вище).
     • Так як результат не дорівнює 1 або -1, ви не можете стверджувати, що n - просте число.

5. 

   5

   Якщо результат не дорівнює 1 або -1, обчисліть a, a, ... і так далі до ad. Якщо один з результатів дорівнює 1 або -1 (mod n), то число n проходить тест Міллера- Рабина і, швидше за все, є простим. Якщо n проходить тест, перевірте відповідь (дивіться наступний крок). Якщо n не проходить будь-який з цих тестів, то n - складене число.
   • Нагадаємо, що в нашому прикладі а = 100, s = 6, d = 5. Продовжіть перевірку таким чином:
     • 100 = 1? 10.
       • 1? 10 (mod 321) = 64. 64 ? 1 або -1. Продовжіть обчислення.
     • 100 = 1? 10.
       • 1? 10 (mod 321) = 244. 244 ? 1 або -1.
     • Тут ви можете закінчити обчислення. s - 1 = 6 - 1 = 5. Ви досягли граничного значення 4d = 2. Оскільки жоден з розрахунків не дав 1 або -1, ви можете з упевненістю заявити, що n = 321 - складене число.

6. 

   6

   Якщо n проходить тест Міллера- Рабіна, повторіть тест з різними значеннями «а», щоб упевнитися в правильності відповіді. Якщо n - просте число, воно пройде тест з будь-яким значенням «а». Якщо n - складене число, не менше трьох чвертей значень «а» не пройдуть тест. Тому тест Міллера- Рабина є більш надійним, ніж тест Ферма, в якому складені числа Кармайкла проходять тест при будь-якому значенні «а».

Метод 4 з 4: Китайська теорема про залишки

1. 

   1

   Виберіть два числа - одне складене, а другий для перевірки того, що воно просте.
   • Число1 = 35
   • Число2 = 97

2. 

   2

   Виберіть два нерівних числа (значення), які більше нуля і менше Чісла1 і Чісла2.
   • Значення1 = 1
   • Значення2 = 2

3. 

   3

   Обчисліть MMI (математичну мультипликативную інверсію) для Чісла1 і Чісла2.
   • Обчисліть MMI.
     
     
     
     • MMI1 = Число2 ^ -1 Mod Число1
     • MMI2 = Число1 ^ -1 Mod Число2
   • Тільки для простих чисел (це дасть число для складених чисел, але воно не буде його MMI):
     • MMI1 = (Число2 ^ (Чісло1-2))% Число1
     • MMI2 = (Число1 ^ (Чісло2-2))% Число2
   • Наприклад:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97

4. 

   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
   • Обчисліть парні Число1 - 2
     • 35 -2 = 33 (10001) за основою 2
     • MMI1 = F (33) = F (32) * F (1) Mod 35
     • MMI1 = F (33) = 1 * 27 Mod 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 Mod 97 = 35
     • F (8) = F (4) * F (4)% Число2 = 35 * 35 Mod 97 = 61
     • F (16) = F (8) * F (8)% Число2 = 61 * 61 Mod 97 = 35
     • F (32) = F (16) * F (16)% Число2 = 35 * 35 Mod 97 = 61
     • F (64) = F (32) * F (32)% Число2 = 61 * 61 Mod 97 = 35
     • F (128) = F (64) * F (64)% Число2 = 35 * 35 Mod 97 = 61
   • Обчисліть парні Число2 - 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. 

   5

   Обчисліть (значення1 * Число2 * MMI1 + значення2 * Число1 * MMI2)% (Число1 * Число2).
   • Відповідь = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Відповідь = (2619 + 4270)% 3395
   • Відповідь = 99

6. 

   6

   Перевірте, що Число1 не є простим.
   • Обчисліть (Відповідь - значення1)% Число1
   • 99 -1% 35 = 28
   • Так як 28 більше 0, то 35 не є простим числом.

7. 

   7

   Перевірте, що Число2 є простим.
   • Обчисліть (Відповідь - значення2)% Число2
   • 99 - 2% 97 = 0
   • Так як 0 дорівнює 0, то 97 - швидше за все просте число.

8. 

   8

   Повторіть кроки з 1 по 7, по крайней мере, ще два рази.
   • Якщо в кроці 7 ви отримали 0:
     • Використовуйте інше Число1, якщо Число1 не є простим.
     • Використовуйте інше Число1, якщо Число1 є простим. У цьому випадку в кроках 6 і 7 ви повинні отримати 0.
     • Використовуйте різні значення1 і значення2.
   • Якщо в кроці 7 ви постійно отримуєте 0, то з дуже великою ймовірністю Число2 є простим.
   • Кроки з 1 по 7 можуть призвести до помилки, якщо Число1 не є простим, а Число2 є дільником Чісла1. Описаний метод працює у всіх випадках, коли обидва числа є простими.
   • Причина, по якій необхідно повторювати кроки з 1 по 7: в деяких випадках, навіть якщо Число1 і Число 2 не є простими, в кроці 7 ви отримаєте 0 (для одного або обох чисел). Це рідкісний випадок-ласка інше Число1 (складене), якщо Число2 не є простим- тоді Число2 не буде рівних нулю в кроці 7 (за винятком випадку, коли Число1 є дільником Чісла2 - тут прості числа завжди будуть рівні нулю за крок 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
• Хоча у випадку великих чисел перебір дільників є трудомістким способом перевірки, він досить ефективний у разі малих чисел. Навіть у випадку великих чисел починають з тестування малих дільників, а потім переходять до більш складних методів перевірки простоти чисел (якщо малі подільники не знайдені).

Що вам знадобиться

• Папір, ручка, комп`ютер.