Совет 1: Что такое простое число

Простым числом называется натуральное число, которое делится только на единицу и само на себя. Все прочие числа, помимо единицы, являются составными. Свойства простых чисел изучает наука под названием теория чисел.
Инструкция
1
Согласно основной теореме арифметики, любое натуральное число, которое больше единицы, может быть разложено на произведение простых чисел. Исходя из этого, можно сделать вывод о том, что простые числа представляют собой определенные «блоки» для натуральных чисел.
2
Операцию представления натурального числа в виде произведения простых называют факторизацией или разложением на простые множители. Полиномиальные алгоритмы разложения чисел неизвестны, но также нет доказательств того, что в природе они не существуют.
3
На сложности вычислений, связанных с факторизацией чисел, основаны некоторые криптосистемы, например, одной из известных является RSA. Для квантовых компьютеров существует алгоритм Шора, который позволяет осуществлять факторизацию чисел с полиномиальной сложностью.
4
Существуют алгоритмы, с помощью которых можно осуществлять поиск, а также распознавать простые числа. Самыми простыми из них являются решето Эратосфена, решето Аткина, решето Сундарама. На деле же часто встает задача не получения простых чисел, а проверки числа на то, является ли оно простым. Алгоритмы, призванные решать подобные задачи, именуются тестами простоты.
5
Еще Евклидом был доказан тот факт, что простых чисел существует бесконечно много. Суть его доказательства, представленного в книге «Начала», заключается в следующем. Пусть существует конечное число простых чисел. Перемножим их, после чего прибавим к ним единицу. Число, которое получилось, не может быть разделено ни на какое простое число из конечного набора без остатка (он будет равен 1). В таком случае это число делится на простое число, которое не входит в состав представленного конечного набора. Помимо этого, существуют также и другие математические доказательства бесконечности простых чисел.

Совет 2: Как определить простое число

Простыми числами называются те целые числа, которые не делятся без остатка ни на какое другое число, кроме единицы и себя самого. В силу разных причин они с древности интересовали математиков. Это привело к развитию разных способов проверки, является ли заданное число простым.
Инструкция
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, а значит и делителями заданного числа они не являются.
Обратите внимание
Признаки делимости на другие простые числа гораздо сложнее, и в большинстве случаев проще попытаться разделить заданное число на предполагаемый делитель вручную.
Источники:
  • Элементарная математика — признаки делимости
Видео по теме
Поиск
Совет полезен?
Комментарии 1
Пожаловаться
написал
число 121 состоит из квадрата простого числа 11
сумма нечетных цифр числа 121 = 1+1 = 2
сумма его четных цифр тоже = 2
разность их = 0
делится ли 0 на 11?
Добавить комментарий к статье
Осталось символов: 500