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


 

Теорія простих чисел хвилює математиків багато століть. Відомо, що їх безліч, але тим не менше до сих пір не знайдено навіть формули, яка давала б одні прості числа.



Інструкція

  1. Нехай за умовою завдання вам задано число N, яке необхідно перевірити на простоту. Для початку переконайтеся, що N не має самих тривіальних дільників, тобто не ділиться на 2 і 5. Для цього перевірте, що остання цифра числа не дорівнює 0, 2, 4, 5, 6 або 8. Таким чином, просте число може закінчуватися лише на 1, 3, 7 або 9.
  2. Підсумуйте цифри числа N. Якщо сума цифр ділиться на 3, то саме число N ділитиметься на 3 і, отже, не є простим. Походимо чином перевіряється подільність на 11 — треба підсумувати цифри числа зі зміною знака, по черзі підсумовуючи або віднімаючи кожну наступну цифру з результату. Якщо результат буде ділитися на 11 (або дорівнювати нулю), то і вихідне число N ділиться на 11. Приклад: для N = 649 знакопеременная сума цифр М = 6 — 4 +9 = 11, тобто це число ділиться на 11. І дійсно, 649 = 11.59.
  3. Введіть своє число на сайті
  4. Якщо звернутися до інтернет-ресурсів з якоїсь причини можливості немає, доведеться вирішувати задачу перебором множників — істотно більш ефективного методу до цих пір не знайдено. Вам потрібно перебрати прості (або все) множники від 7 до √ N і спробувати зробити розподіл. N виявиться простим, якщо ні на один з цих дільників не розділиться нацело.
  5. Щоб не займатися перебором вручну, можна написати власну програму. Ви можете скористатися улюбленим мовою програмування, скачавши для нього математичну бібліотеку, в якій є функція визначення простих чисел. Якщо бібліотека вам недоступна, доведеться діяти перебором, як описано в пункті 4. Найзручніше перебирати числа виду 6k ± 1, так як всі прості числа крім 2 і 3 представимо в такому вигляді.