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

Простыми числами называются те целые числа, которые не делятся без остатка ни на какое другое число, кроме единицы и себя самого. В силу разных причин они с древности интересовали математиков. Это привело к развитию разных способов проверки, является ли заданное число простым.

Инструкция

1. Поскольку простое число по определению не должно делиться ни на какое другое, кроме себя самого, очевидный способ проверки числа на простоту — попытка разделить его без остатка на все числа, меньшие его. Именно этот способ обычно выбирают создатели компьютерных алгоритмов.
2. Однако перебор может оказаться достаточно долгим, если, скажем, на простоту нужно проверить число вида 136827658235479371. Поэтому стоит обратить внимание на правила, способные заметно сократить время вычислений.
3. Если число составное, то есть представляет собой произведение простых сомножителей, то среди этих сомножителей обязательно должен найтись хотя бы один, который будет меньше квадратного корня из заданного числа. Ведь произведение двух чисел, каждое из которых больше квадратного корня из некоторого X, будет заведомо больше X, и эти два числа никак не могут быть его делителями.
4. Поэтому даже при простом переборе можно ограничиться проверкой только тех целых чисел, которые не превышают квадратный корень из заданного числа, округленный в большую сторону. Например, проверяя число 157, вы перебираете возможные множители только от 2 до 13.
5. Если у вас нет под рукой компьютера, и число на простоту приходится проверять вручную, то и здесь на помощь приходят простые и очевидные правила. Больше всего вам поможет знание уже известных простых чисел. Ведь проверять отдельно делимость на составные числа нет смысла, если можно проверить делимость на их простые множители.
6. Четное число по определению не может быть простым, поскольку делится на 2. Поэтому, если последняя цифра числа четна, то оно заведомо составное.
7. Числа, делящиеся на 5, всегда оканчиваются пятеркой или нулем. Взгляд на последнюю цифру числа поможет их отсеять.
8. Если число делится на 3, то и сумма его цифр тоже обязательно делится на 3. Например, сумма цифр числа 136827658235479371 равна 1 + 3 + 6 + 8 + 2 + 7 + 6 + 5 + 8 + 2 + 3 + 5 + 4 + 7 + 9 + 3 + 7 + 1 = 87. Это число делится на 3 без остатка: 87 = 29*3. Следовательно, и наше число тоже делится на 3 и является составным.
9. Очень прост также признак делимости на 11. Нужно из суммы всех нечетных цифр числа вычесть сумму всех четных его цифр. Четность и нечетность определяется счетом с конца, то есть с единиц. Если получившаяся разность делится на 11, то и все заданное число тоже на него делится. Например, пусть дано число 2576562845756365782383. Сумма его четных цифр равна 8 + 2 + 7 + 6 + 6 + 7 + 4 + 2 + 5 + 7 + 2 = 56. Сумма нечетных: 3 + 3 + 8 + 5 + 3 + 5 + 5 + 8 + 6 + 6 + 5 = 57. Разность между ними равна 1. Это число не делится на 11, а следовательно, 11 не является делителем заданного числа.
10. Проверить делимость числа на 7 и 13 можно аналогичным способом. Разбейте число на тройки цифр, начиная с конца (так делают при типографской записи для удобства чтения). Число 2576562845756365782383 превращается в 2 576 562 845 756 365 782 383. Просуммируйте числа, стоящие на нечетных местах, и вычтите из них сумму чисел на четных. В данном случае вы получите (383 + 365 + 845 + 576) - (782 + 756 + 562 + 2) = 67. Это число не делится ни на 7, ни на 13, а значит и делителями заданного числа они не являются.