Як перевірити просте чи число
прочитали: 95
Теорія простих чисел хвилює математиків багато століть. Відомо, що їх безліч, але тим не менше до сих пір не знайдено навіть формули, яка давала б одні прості числа.
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
Введіть своє число на сайті https://usi.edu/science/math/prime.html і натисніть кнопку “Check my number”. якщо число просте, програма напише щось на кшталт “59 is prime”, А інакше представить його у вигляді твору множників.
4
Якщо звернутися до інтернет-ресурсів з якоїсь причини можливості немає, доведеться вирішувати задачу перебором множників - істотно більш ефективного методу до цих пір не знайдено. Вам потрібно перебрати прості (або все) множники від 7 до &radic-N і спробувати зробити розподіл. N виявиться простим, якщо ні на один з цих дільників не розділені остачі.
5
Щоб не займатися перебором вручну, можна написати власну програму. Ви можете скористатися улюбленим мовою програмування, скачавши для нього математичну бібліотеку, в якій є функція визначення простих чисел. Якщо бібліотека вам недоступна, доведеться діяти перебором, як описано в пункті 4. Найзручніше перебирати числа виду 6k ± 1, так як всі прості числа крім 2 і 3 представимо в такому вигляді.