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

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