Инструкция
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 представимы в таком виде.