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

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

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

Самые известные способы найти список простых чисел вплоть до некоторого значения-- это решето Эратосфена, решето Сундарама и решето Аткина. Для того, чтобы проверить, является ли данное число простым, существуют тесты простоты
Как известно, простые числа делятся только нацело
Вам понадобится
  • Калькулятор, лист бумаги и карандаш (ручка)
Инструкция
1
Способ 1. Решето Эратосфена.
По этому методу, чтобы найти все простые числа не больше определенного значения Х, необходимо выписать подряд все целые числа от одного до Х. Возьмем число 2 как первое простое число. Вычеркнем из списка все числа, делящиеся на 2. Затем возьмем следующее после двойки, не вычеркнутое число, и вычеркнем из списка все числа, делящиеся на взятое нами число. И далее каждый раз будем брать следующее не вычеркнутое число и вычеркивать из списка все числа, делящиеся на взятое нами число. И так до тех пор пока выбранное нами число не станет больше, чем Х/2. Все оставшиеся в списке не вычеркнутые числа являются простыми
2
Способ 2. Решето Сундарама.
Из ряда натуральных чисел от 1 до N исключаются все числа вида
х + у + 2ху,
где индексы х (не больший у) пробегают все натуральные значения, для которых х+у+2ху не больше N, а именно значения х=1, 2,...,((2N+1)1/2-1)/2 и х=у, х+1,...,(N-х)/(2х+1)ю. Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все нечётные простые числа в ряду от одного до 2N+1.
3
Способ 3. Решето Аткина.
Решето Аткина представляет собой сложный современный алгоритм нахождения всех простых чисел до заданного значения Х. Основная суть алгоритма состоит в представлении простых чисел как целых с нечетным числом представлений в данных квадратных формах. Отдельный этап алгоритма отсеивает числа, кратные квадратам простых чисел в интервале от 5 до Х.
4
Тесты простоты.
Тесты простоты-- это алгоритмы, позволяющие определить, является ли конкретное число Х простым.
Один из самых простых, но и трудоемких тестов-- это перебор делителей. Он состоит в преборе всех целых чисел от 2 до квадратного корня из Х и в вычислении остатка от деления Х на каждое из этих чисел. Если остаток от деления числа Х на некоторое число (больше 1 и меньше Х) равен нулю, то число Х является составным. Если выявляется, что число Х невозможно сократить без остатка ни на одно из чисел, кроме единицы и самого себя, то число Х простое.
Кроме этого способа существует также большое количество других тестов для тестирования простоты числа. Большинство этих тестов являются вероятностными и используются в криптографии. Единственный тест, гарантирующий получение ответа (тест AKS) очень сложен в вычислении, что затрудняет его практическое применение
Совет полезен?
Поиск
Добавить комментарий к статье
Осталось символов: 500