Главная Войти О сайте

Как проверить простое ли число

Теория простых чисел волнует математиков многие века. Известно, что их бесконечное множество, но тем не менее до сих пор не найдено даже формулы, которая давала бы одни простые числа.Как проверить простое ли число

Пусть по условию задачи вам задано число 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 = 11·59.

Введите свое число на сайте http://www.usi.edu/science/math/prime.html и нажмите кнопку “Check my number”. Если число простое, программа напишет что-то вроде “59 is prime”, а иначе представит его в виде произведения множителей.

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

Чтобы не заниматься перебором вручную, можно написать собственную программу. Вы можете воспользоваться любимым языком программированию, скачав для него математическую библиотеку, в которой есть функция определения простых чисел. Если библиотека вам недоступна, придется действовать перебором, как описано в пункте 4. Удобнее всего перебирать числа вида 6k±1, так как все простые числа кроме 2 и 3 представимы в таком виде.


CompleteRepair.Ru