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

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

Інструкція

Нехай за умовою завдання вам задано число N, яке необхідно перевірити на простоту. Для початку переконайтеся, що N не має самих тривіальних дільників, тобто не ділиться на 2 і 5. Для цього перевірте, що остання цифра числа не дорівнює 0, 2, 4, 5, 6 або 8. Таким чином, просте число може закінчуватися лише на 1, 3, 7 або 9.

Підсумуйте цифри числа N. Якщо сума цифр ділиться на 3, то саме число N буде ділитися на 3 і, отже, не є простим. Походимо чином перевіряється подільність на 11 - треба підсумувати цифри числа зі зміною знака, по черзі підсумовуючи або віднімаючи кожну наступну цифру з результату. Якщо результат буде ділитися на 11 (або дорівнювати нулю), то і вихідне число N ділиться на 11. Приклад: для N = 649 знакозмінна сума цифр М = 6 - 4 +9 = 11, тобто це число ділиться на 11. І дійсно, 649 = 11middot-59.

Введіть своє число на сайті https://www.usi.edu/science/math/prime.html і натисніть кнопку "Check my number". Якщо число просте, програма напише щось на кшталт "59 is prime", а інакше представить його у вигляді добутку множників.

Якщо звернутися до інтернет-ресурсів з якоїсь причини можливості немає, доведеться вирішувати задачу перебором множників - істотно більш ефективного методу досі не знайдено. Вам потрібно перебрати прості (або всі) множники від 7 до radic-N і спробувати зробити розподіл. N виявиться простим, якщо ні на один з цих дільників не розділені остачі.

Щоб не займатися перебором вручну, можна написати власну програму. Ви можете скористатися улюбленим мовою програмування, скачавши для нього математичну бібліотеку, в якій є функція визначення простих чисел. Якщо бібліотека вам недоступна, доведеться діяти перебором, як описано в пункті 4. Найзручніше перебирати числа виду 6k ± 1, так як всі прості числа крім 2 і 3 представимо в такому вигляді.