Прості числа

Просте число – це додатне натуральне число, яке має лише два ділених натуральних чисел – одне і саме.

Протилежними простим числам є складені числа. Складене число – це позитивне нутричне число, яке має принаймні один позитивний дільник, відмінний від одного або самого.

Число 1 за визначенням не є простим числом – воно має лише один дільник.

Число 0 не є простим числом – воно не є додатним числом і має нескінченну кількість дільників.

Число 15 має дільники 1,3,5,15, оскільки:

Отже, 15 не є простим числом.

Число 13 має лише два дільники 1,13.

Список простих чисел

Список простих чисел до 100:

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, .

Чи є 0 простим числом?

Число 0 не є простим числом.

Нуль не є додатним числом і має нескінченну кількість дільників.

Чи є 1 простим числом?

Число 1 за визначенням не є простим числом.

У одного є один дільник – сам.

Чи є простим числом 2?

У двох є 2 дільники натуральних чисел – 1 і 2:

Дивіться також

Прості числа та складові числа. Таблиця простих чисел.

Просте число — натуральне число, що має рівно два різні натуральні дільники — одиницю і самого себе [1] .

Тобто число x є простим, якщо воно більше 1 і при цьому ділиться без залишку тільки на 1 і x .

Складове число — натуральне число, більше 1, яке не є простим.

Кожне складове число є добутком двох чи більше простих чисел.

• одиницю – має один натуральний дільник,
• прості числа – мають два натуральні дільники,
• складові числа – мають більше двох натуральних дільників.

2 — просте число (ділиться на 2 та 1)

3 — просте число (ділиться на 3 та 1)

4 — складове число (ділиться на 4, 2 та 1)

5 — просте число (ділиться на 5 м 1)

6 — складове число (ділиться на 6, 3, 2 та 1)

7 — просте число (ділиться на 7 та 1)

8 — складове число (ділиться на 8, 4, 2 та 1)

9 — складове число (ділиться на 9, 3 та 1)

10 — складове число (ділиться на 10, 5, 2 та 1)

Таблиця простих чисел від 2 до 1000

Таблиця простих чисел від 1000 до 10000

1 Простое число // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1977. — Т. 4.

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

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

Кроки

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

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

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

• Наприклад, перевіримо число 11. У цьому випадку розділимо (без остачі) 11 на 3, 4, 5, 6, 7, 8, 9, 10. Так як жодне з цих чисел не ділить (без остачі) 11, то число 11 – просте число.

• Пояснення цього принципу. Розглянемо множники 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, тому воно – просте.
  • Це означає, що всі парні подільники та все подільники, кратні простим числам, можуть бути опущені.
  • Наприклад, перевіримо число 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.
    • Одним із способів обчислення буде обчислити a, а потім розділити результат на n, а в якості відповіді записати залишок поділу. У цьому випадку рекомендується використовувати спеціалізовані калькулятори з функцією модуля, так як вони миттєво обчислюють залишок при діленні великих чисел.
    • У нашому прикладі, при діленні 3/100 виходить залишок 1. Таким чином, 3 (mod 100) = 1.
    • У нашому прикладі вручну обчисліть 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 (такий же результат був отриманий при обчисленні на калькуляторі).

        Метод 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, що значно ускладнить обчислення.
        • У нашому прикладі для n = 321: a (mod n) = 100 (mod 321). 100 = 10,000,000,000 (mod 321) = 313. Для знаходження залишку 100/321 використовуйте спеціалізований калькулятор або розрахунок вручну (описаний вище).
          • Так як результат не дорівнює 1 або -1, ви не можете стверджувати, що n – просте число.
          • Нагадаємо, що в нашому прикладі а = 100, s = 6, d = 5. Продовжіть перевірку таким чином:
            • 100 = 1? 10.
              • 1? 10 (mod 321) = 64. 64 ? 1 або -1. Продовжіть обчислення.
              • 1? 10 (mod 321) = 244. 244 ? 1 або -1.

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

              1. 1 Виберіть два числа – одне складене, а другий для перевірки того, що воно просте.
                 • Число1 = 35
                 • Число2 = 97
              • MMI1 = (Число2 ^ (Чісло1-2))% Число1
              • MMI2 = (Число1 ^ (Чісло2-2))% Число2
              • MMI1 = (97 ^ 33)% 35
              • MMI2 = (35 ^ 95)% 97
              • Для 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
                • 35 -2 = 33 (10001) за основою 2
                • MMI1 = F (33) = F (32) * F (1) Mod 35
                • MMI1 = F (33) = 1 * 27 Mod 35
                • MMI1 = 27
                • 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
                • 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
                • Відповідь = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
                • Відповідь = (2619 + 4270)% 3395
                • Відповідь = 99
                • Обчисліть (Відповідь – значення1)% Число1
                • 99 -1% 35 = 28
                • Так як 28 більше 0, то 35 не є простим числом.
                • Обчисліть (Відповідь – значення2)% Число2
                • 99 – 2% 97 = 0
                • Так як 0 дорівнює 0, то 97 – швидше за все просте число.
                • Якщо в кроці 7 ви отримали 0:
                  • Використовуйте інше Число1, якщо Число1 не є простим.
                  • Використовуйте інше Число1, якщо Число1 є простим. У цьому випадку в кроках 6 і 7 ви повинні отримати 0.
                  • Використовуйте різні значення1 і значення2.

                  Поради

                  • Прості числа від 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
                  • Хоча у випадку великих чисел перебір дільників є трудомістким способом перевірки, він досить ефективний у разі малих чисел. Навіть у випадку великих чисел починають з тестування малих дільників, а потім переходять до більш складних методів перевірки простоти чисел (якщо малі подільники не знайдені).

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