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

Простые числа – это числа, которые делятся только на себя и на 1; все остальные числа называются составными числами. Существует множество способов определения того, является ли число простым. Некоторые способы являются относительно простыми, но они не подходят для больших чисел. Другие способы, применимые для больших чисел, фактически представляют собой вероятностные алгоритмы, которые иногда ошибочно характеризуют число как простое или составное.

Метод 1 Перебор делителей

Перебор делителей – самый легкий способ определить простоту числа. В случае малых чисел это, пожалуй, также и самый быстрый способ. Он основан на определении простого числа: число является простым, если оно не имеет делителей кроме самого себя и единицы.

1. 1 Пусть n – проверяемое число. Согласно этому методу вы должны разделить число n на все возможные целые делители. При больших значениях n, например, n = 101, проверка каждого делителя займет много времени. Но существуют способы уменьшить количество делителей, которые нужно проверить.
2. 2 Определите, является ли число n четным. Любое четное число делится на 2. Если число n — четное, то можно сразу заявить, что оно не является простым (то есть является составным числом). Для быстрого определения четности числа обратите внимание на его последнюю цифру. Если последняя цифра 2, 4, 6, 8,0, то число является четным и не является простым.
3. Единственное исключение из этого правила — число 2. Так как оно делится нацело только на себя и на 1, то число 2 – простое число. Таким образом, число 2 является единственным четным простым числом.
4. 3 Разделите n на каждое число от 2 до n-1. Так как делитель меньше делимого, то проверка всех делителей меньших n и больших 2 должна показать, является ли n простым числом. Вы начинаете с числа большего 2, потому что четные числа (которые кратны 2) не являются простыми числами. Это далеко не самый эффективный способ тестирования чисел на простоту, но здесь существует несколько методов оптимизации проверки.
5. Например, проверим число 11. В этом случае разделим (нацело) 11 на 3, 4, 5, 6, 7, 8, 9, 10. Так как ни одно из этих чисел не делит (нацело) 11, то число 11 – простое число.
6. 4 Чтобы сэкономить время, проверьте делители до округленного значения квадратного корня (n). Проверка всех делителей от 2 до n-1 может занять много времени. Например, если вы хотите проверить число 103, то вам придется протестировать следующие делители: 3, 4, 5, 6, 7. и так далее вплоть до 102! Но этого можно избежать – проверьте только делители от 2 до округленного значения квадратного корня (n).
7. Объяснение этого принципа. Рассмотрим множители 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2, 100 × 1. Обратите внимание, что после пары множителей 10 × 10 все пары множителей повторяются (только множители в этих парах переставлены местами). Поэтому вы можете игнорировать делители числа n большие, чем квадратный корень (n).
8. Например, проверим n = 37. Не нужно тестировать все делители от 3 до 36. Вместо этого проверьте делители между 2 и округленным значением квадратного корня (37).
9. Квадратный корень (37) = 6,08. Округлите это число до 7.
10. 37 не делится на 3, 4, 5, 6, 7, поэтому оно — простое.
11. 5 Для дальнейшей экономии времени тестируйте только простые делители. По определению любое составное число может быть выражено как произведение двух или более простых чисел. Поэтому деление числа n на составной делитель – лишняя операция, повторяющая многократное деление числа n на простые делители. Таким образом, вы можете еще больше сузить тестируемый ряд делителей.
12. Это означает, что все четные делители и все делители, кратные простым числам, могут быть опущены.
13. Например, проверим число 103. Квадратный корень из 103 округляется до 11. Простые делители от 2 до 11 это 3, 5, 7, 11. Делители 4, 6, 8, 9, 10 можно опустить (9 кратно 3, а все остальные делители – четные числа). Таким образом, вы уменьшили ряд тестируемых делителей до четырех чисел.
14. Делители 3, 5, 7, 11 не делят (нацело) число 103, поэтому оно — простое.

Метод 2 Тест Ферма

В 1640 году французский математик Пьер Ферма впервые сформулировал теорему (малая теорема Ферма), которая используется при определении простоты числа. Фактически, тест Ферма служит для определения составных чисел, а не простых. Этот тест с уверенностью определяет, является ли число составным, или определяет, что число «скорее всего» простое. Тест Ферма полезен в случаях, когда перебор делителей непрактичен и когда доступен список чисел, являющихся исключениями из теоремы.

1. 1 Пусть n – проверяемое число. Как отмечалось выше, иногда тест ложно идентифицирует составные числа как простые. Поэтому необходимо проверить ответ (способ проверки ответа описан ниже).
2. 2 Выберите любое целое число «а» от 2 до n-1 (включительно).
3. Например, проверим на простоту число 100. Допустим, а = 3.
4. 3 Вычислите an (mod n). Вычисление этого выражения потребует некоторых знаний из модульной арифметики. В модульной арифметике при достижении определенного значения, называемого модулем, отсчет чисел начинается с нуля. Представьте это как часы: час после полудня — это 1:00, а не 13:00, то есть время после полудня отсчитывается с нуля. Модуль обозначается как mod n. Таким образом, вычислите a n (mod n).
5. Одним из способов вычисления будет вычислить a n , а затем разделить результат на n, а в качестве ответа записать остаток деления. В этом случае рекомендуется использовать специализированные калькуляторы с функцией модуля , так как они мгновенно вычисляют остаток при делении больших чисел.
6. В нашем примере, при делении 3 100 /100 получается остаток 1. Таким образом, 3 100 (mod 100) = 1.
7. 4 Если у вас нет специализированного калькулятора, при вычислении остатка вручную используйте экспоненциальную запись числа.
8. В нашем примере вручную вычислите 3 100 (mod 100). 3 100 = 515377520732011331036461129765621272702107522001 – огромное число, с которым трудно работать. Вместо того, чтобы работать с 48-значным числом, представьте 3 100 как (((((((3 2 )*3) 2 ) 2 ) 2 )*3) 2 ) 2 . Напомним, что при возведении степени в степень показатели перемножаются: ((x y ) z = x yz ).
9. Теперь определите остаток. В (((((((3 2 )*3) 2 ) 2 ) 2 )*3) 2 ) 2 начните решение с внутренних скобок и каждый раз результат делите на 100. При получении остатка используйте его в дальнейших расчетах (а не в качестве ответа).
10. (((((((9)*3) 2 ) 2 ) 2 )*3) 2 ) 2 — 9/100 – остатка нет.
11. ((((((27) 2 ) 2 ) 2 )*3) 2 ) 2 — 27/100 – остатка нет.
12. (((((729) 2 ) 2 )*3) 2 ) 2 — 729/100 = 7(ост.29). Остаток 29. Продолжите вычисления с числом 29.
13. ((((29 2 =841) 2 )*3) 2 ) 2 — 841/100 = 8(ост.41). Остаток 41. Продолжите вычисления с числом 41.
14. (((41 2 = 1681)*3) 2 ) 2 — 1681/100 = 16(ост.81). Остаток 81. Продолжите вычисления с числом 81.
15. ((81*3 = 243) 2 ) 2 — 243/100 = 2(ост. 43). Остаток 43. Продолжите вычисления с числом 43.
16. (43 2 = 1849) 2 — 1849/100 = 18(ост.49). Остаток 49. Продолжите вычисления с числом 49.
17. 49 2 = 2401 — 2401/100 = 24(ост.1). Конечный остаток 1. Таким образом, 3 100 (mod 100) = 1 (такой же результат был получен при вычислении на калькуляторе).
18. 5 Проверьте равенство:an (mod n) = a (mod n). Если оно не соблюдено, то n – составное число. Если оно соблюдено, то n, скорее всего, простое число (но не обязательно). Повторите тест с разными значениями «а», чтобы удостовериться в правильности ответа. Но есть составные числа, удовлетворяющие условию Ферма при любых значениях «а». Они называются числами Кармайкла (самое малое из них — число 561).
19. В нашем примере 3 100 (mod 100) = 1, а 100 (mod 100 ) = 0. Таким образом, 1 ≠ 0 и 100 – составное число.
20. 6 Используйте числа Кармайкла в качестве гарантии правильности ответа. Числа Кармайкла имеют вид (6k + 1)(12k + 1)(18k + 1) для целых значений k, когда каждый делитель является простым. Вы можете найти полный список чисел Кармайкла в интернете.

Метод 3 Тест Миллера-Рабина

Тест Миллера-Рабина эффективно определяет, является ли число составным (и лучше обрабатывает исключения, такие как числа Кармайкла).

1. 1 Пусть n — нечетное число, которое нужно протестировать на простоту.
2. 2 Запишите n-1 в виде 2 s × d, где d – нечетное число. Если n – простое, то оно должно быть нечетным. Поэтому n-1 – четное. Так как n-1 – четное число, то оно может быть представлено в виде произведения числа 2 в некоторой степени на нечетное число. Например, 4 = 2 2 × 1, 80 = 2 4 × 5 и так далее.
3. Например, определите простоту числа n = 321. 321 — 1 = 320, а 320 = 2 6 × 5. То есть s=6 и d=5.
4. Например, возьмем более сложное число n = 371. 371 — 1 = 370, а 370 = 2 1 × 185. То есть d=185, что значительно усложнит вычисления.
5. 3 Возьмите любое число «а» между 2 и n-1.
6. В нашем примере для n = 321 выберите а = 100.
7. 4 Вычислите ad (mod n). Если ad = 1 или -1 (mod n), то число n проходит тест Миллера-Рабина и, скорее всего, является простым. Однако этот тест, как и тест Ферма, не может определить простоту числа с абсолютной уверенностью.
8. В нашем примере для n = 321: a d (mod n) = 100 5 (mod 321). 100 5 = 10,000,000,000 (mod 321) = 313. Для нахождения остатка 100 5 /321 используйте специализированный калькулятор или расчет вручную (описанный выше).
9. Так как результат не равен 1 или -1, вы не можете утверждать, что n – простое число.
10. 5 Если результат не равен 1 или -1, вычислите a 2d , a 4d , ... и так далее до a 2 s-1 d . Если один из результатов равен 1 или -1 (mod n), то число n проходит тест Миллера- Рабина и, скорее всего, является простым. Если n проходит тест, проверьте ответ (смотрите следующий шаг). Если n не проходит любой из этих тестов, то n – составное число.
11. Напомним, что в нашем примере а=100, s=6, d=5. Продолжите проверку следующим образом:
12. 100 2d = 10 = 1 × 10 20 .
13. 1 × 10 20 (mod 321) = 64. 64 ≠ 1 или -1. Продолжите вычисления.
14. 100 4d = 20 = 1 × 10 40 .
15. 1 × 10 40 (mod 321) = 244. 244 ≠ 1 или -1.
16. Здесь вы можете закончить вычисления. s — 1 = 6 — 1 = 5. Вы достигли предельного значения 4d = 2 2 . Так как ни один из расчетов не дал 1 или -1, вы можете с уверенностью заявить, что n = 321 – составное число.
17. 6 Если n проходит тест Миллера- Рабина, повторите тест с разными значениями «а», чтобы удостовериться в правильности ответа. Если n – простое число, оно пройдет тест с любым значением «а». Если n – составное число, не менее трех четвертей значений «а» не пройдут тест. Поэтому тест Миллера- Рабина является более надежным, чем тест Ферма, в котором составные числа Кармайкла проходят тест при любом значении «а».

Условие задачи 2.30

Задача 2.30
Дан одномерный массив А, состоящий из натуральных чисел. Вывести на экран количество простых чисел в массиве.

Для начала напомню, что такое простые числа.

Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя — единицу и самого себя.

То есть если число делится без остатка только на 1 и на самого себя, то такое число является простым.

Например, простыми числами являются 2, 3, 5 и т.п.

А вот 4 уже не является простым, так как делится без остатка не только на 1 и 4, но ещё и на 2.

Если вы подзабыли, что такое натуральное число, то см. здесь.

А теперь перейдём к задаче. По сути нам нужна программа, определяющая простые числа. А уж перебрать элементы массива в цикле и проверить их значения — это дело техники. Заодно мы можем не только подсчитать, но и вывести на экран простые числа массива.

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

Алгоритм решения с подробным разбором приведу на Паскале. Решение на С++ можете посмотреть в примере программы на С++.

ВАЖНО!
На этом многие могут ошибиться. В определении сказано, что простое число имеет ровно два различных делителя. Следовательно, число 1 не является простым (также не является простым, так как ноль можно делить на любые числа).

Проверять, является ли число простым, будем с помощью функции, которую сами и создадим. Эта функция будет возвращать TRUE, если число простое.

В функции сначала будем проверять, не является ли число меньше двух. Если да, то это уже не простое число. Если же число равно 2 или 3, то оно является однозначно простым и делать какие-то дополнительные проверки не требуется.

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

Проверять, делится ли число на самоё себя нет смысла (поэтому цикл длится только до N-1).

Саму функцию здесь приводить не буду — посмотрите её в примерах программ.

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

Простые и составные числа – определения и примеры

Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.

Простыми числами называют целые числа, которые больше единицы и имеют два положительных делителя, то есть себя и 1 .

Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.

Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.

Простые числа – это натуральные числа, имеющие только два положительных делителя.

Составное число – это натуральное число, имеющее более двух положительных делителей.

Любое число, которое больше 1 является либо простым, либо составным. Из свойства делимости имеем, что 1 и число а всегда будут делителями для любого числа а , то есть оно будет делиться само на себя и на 1 . Дадим определение целых чисел.

Натуральные числа, которые не являются простыми, называют составными.

Простые числа: 2 , 3 , 11 , 17 , 131 , 523 . Они делятся только сами на себя и на 1 . Составные числа: 6 , 63 , 121 , 6697 . То есть число 6 можно разложить на 2 и 3 , а 63 на 1 , 3 , 7 , 9 , 21 , 63 , а 121 на 11 , 11 , то есть его делители будут 1 , 11 , 121 . Число 6697 разложится на 37 и 181 . Заметим, что понятия простых чисел и взаимно простых чисел – разные понятия.

Таблица простых чисел

Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:

Таблица для всех существующих натуральных чисел нереальна, так как их существует бесконечное множество. Когда числа достигают размеров 10000 или 1000000000 , тогда следует задуматься об использовании решета Эратосфена.

Рассмотрим теорему, которая объясняет последнее утверждение.

Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.

Возьмем, что а является натуральным числом, которое больше 1 , b является наименьшим отличным от единицы делителем для числа а . Следует доказать, что b является простым числом при помощи метода противного.

Допустим, что b – составное число. Отсюда имеем, что есть делитель для b , который отличен от 1 как и от b . Такой делитель обозначается как b 1 . Необходимо, чтобы условие 1 b 1 b было выполнено.

Из условия видно, что а делится на b , b делится на b 1 , значит, понятие делимости выражается таким образом: a = b · q и b = b 1 · q 1 , откуда a = b 1 · ( q 1 · q ) , где q и q 1 являются целыми числами. По правилу умножения целых чисел имеем, что произведение целых чисел – целое число с равенством вида a = b 1 · ( q 1 · q ) . Видно, что b 1 – это делитель для числа а . Неравенство 1 b 1 b не соответствует, потому как получим, что b является наименьшим положительным и отличным от 1 делителем а .

Простых чисел бесконечно много.

Предположительно возьмем конечное количество натуральных чисел n и обозначим как p 1 , p 2 , … , p n . Рассмотрим вариант нахождения простого числа, отличного от указанных.

Примем на рассмотрение число р, которое равняется p 1 , p 2 , … , p n + 1 . Оно не равняется каждому из чисел, соответствующих простым числам вида p 1 , p 2 , … , p n . Число р является простым. Тогда считается, что теорема доказана. Если оно составное, тогда нужно принять обозначение p n + 1 и показать несовпадение делителя ни с одним из p 1 , p 2 , … , p n .

Если это было бы не так, тогда, исходя из свойства делимости произведения p 1 , p 2 , … , p n _, получим, что оно делилось бы на p n + 1 . Заметим, что на выражение p n + 1 делится число р равняется сумме p 1 , p 2 , … , p n + 1 . Получим, что на выражение p n + 1 должно делиться второе слагаемое этой суммы, которое равняется 1 , но это невозможно.

Видно, что может быть найдено любое простое число среди любого количества заданных простых чисел. Отсюда следует, что простых чисел бесконечно много.

Так как простых чисел очень много, то таблицы ограничивают числами 100 , 1000 , 10000 и так далее.

Решето Эратосфена

При составлении таблицы простых чисел следует учитывать то, что для такой задачи необходима последовательная проверка чисел, начиная с 2 до 100 . При отсутствии делителя оно фиксируется в таблицу, если оно составное, то в таблицу не заносится.

Если начать с числа 2 , то оно имеет только 2 делителя: 2 и 1, значит, его можно занести в таблицу. Также и с числом 3 . Число 4 является составным, следует разложить его еще на 2 и 2 . Число 5 является простым, значит, можно зафиксировать в таблице. Так выполнять вплоть до числа 100 .

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

Способ при помощи решета Эратосфена считают самым удобным. Рассмотрим на примере таблиц, приведенных ниже. Для начала записываются числа 2 , 3 , 4 , … , 50 .

Теперь необходимо зачеркнуть все числа, которые кратны 2 . Произвести последовательное зачеркивание. Получим таблицу вида:

Далее вычеркиваем все числа, кратные 3 . Получаем таблицу вида:

Переходим к вычеркиванию чисел, кратных 5 . Получим:

Вычеркиваем числа, кратные 7 , 11 . В конечном итоге таблица получает вид

Перейдем к формулировке теоремы.

Наименьший положительный и отличный от 1 делитель основного числа а не превосходит a , где a является арифметическим корнем заданного числа.

Необходимо обозначить b наименьший делитель составного числа а . Существует такое целое число q , где a = b · q , причем имеем, что b ≤ q . Недопустимо неравенство вида b > q , так как происходит нарушение условия. Обе части неравенства b ≤ q следует умножить на любое положительное число b , не равное 1 . Получаем, что b · b ≤ b · q , где b 2 ≤ a и b ≤ a .

Из доказанной теоремы видно, что вычеркивание чисел в таблице приводит к тому, что необходимо начинать с числа , которое равняется b 2 и удовлетворяет неравенству b 2 ≤ a . То есть, если вычеркнуть числа, кратные 2 , то процесс начинается с 4 , а кратных 3 – с 9 и так далее до 100 .

Составление такой таблицы при помощи теоремы Эратосфена говорит о том, что при вычеркивании всех составных чисел, останутся простые, которые не превосходят n . В примере, где n = 50 , у нас имеется, что n = 50 . Отсюда и получаем, что решето Эратосфена отсеивает все составные числа, которые по значению не больше значения корня из 50 . Поиск чисел производится при помощи вычеркивания.

Данное число простое или составное?

Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.

Доказать что число 898989898989898989 является составным.

Сумма цифр заданного числа равняется 9 · 8 + 9 · 9 = 9 · 17 . Значит, число 9 · 17 делится на 9 , исходя из признака делимости на 9 . Отсюда следует, что оно составное.

Такие признаки не способны доказать простоту числа. Если нужна проверка, следует производить другие действия. Самый подходящий способ – это перебор чисел. В течение процесса можно найти простые и составные числа. То есть числа по значению не должны превосходить a . То есть число а необходимо разложить на простые множители. если это будет выполнено, тогда число а можно считать простым.

Определить составное или простое число 11723 .

Теперь необходимо найти все делители для числа 11723 . Необходимо оценить 11723 .

Отсюда видим, что 11723 200 , то 200 2 = 40 000 , а 11 723 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

Для более точной оценки числа 11723 необходимо записать выражение 108 2 = 11 664 , а 109 2 = 11 881 , то 108 2 11 723 109 2 . Отсюда следует, что 11723 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

При разложении получим, что 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 – это все простые числа. Весь данный процесс можно изобразить как деление столбиком. То есть разделить 11723 на 19 . Число 19 является одним из его множителей, так как получим деление без остатка. Изобразим деление столбиком:

Отсюда следует, что 11723 является составным числом, потому как кроме себя и 1 имеет делитель 19 .

Ответ: 11723 является составным числом.