Проверка на простоту числа python

Содержание

1 1 ответ 1
2 Всё ещё ищете ответ? Посмотрите другие вопросы с метками python или задайте свой вопрос.
3 среда, 13 апреля 2011 г.
- 3.1 Тест простоты

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

Простые числа — это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 3 простое, так как нацело делится только на 1 и 3. Число 4 сложное, так как нацело делится не только на 1 и 4, но также на число 2.

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

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

Число 2 является простым, но при этом оно делится на 2. Цикл while определил бы двойку как составное число, что неправильно. Поэтому для числа 2 необходима отдельная проверка.

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

Пример функции, определяющей является ли число простым:

Доброй ночи! Только начал обучение, и тут домашка которую я не могу сделать 6 часов) Домашка собственно звучит так "Написать функцию is_prime, принимающую 1 аргумент — число от 0 до 1000, и возвращающую True, если оно простое, и False — иначе."

a = int(input("Enter a number: ")) print(is_prime(a))

1 ответ 1

Всё ещё ищете ответ? Посмотрите другие вопросы с метками python или задайте свой вопрос.

среда, 13 апреля 2011 г.

Тест простоты

Тест простоты — алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты.
Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, тестирование простоты значительно легче факторизации заданного числа.

*-Нравится статья? Кликни по рекламе! 🙂

Мы уже разобрали методы выбора всех простых чисел, до определенного, в статье Простые числа. Пришло время рассмотреть ряд алгоритмов, под общим названием — "Тесты простоты":

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на m и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.
Примечание: если у n есть некоторый делитель p, то n/p так же будет делителем, причем одно из этих чисел не превосходит .

Реализация на Python:

2.) Теорема Вильсона
Теорема теории чисел, которая утверждает, что

p — простое число тогда и только тогда, когда (p − 1)! + 1 делится на p

Практическое использование теоремы Вильсона для определения простоты числа нецелесообразно из-за сложности вычисления факториала. Таким образом, время выполнения данного алгоритма = поиску факториала. Алгоритм поиска факториала мы уже рассматривали.
Реализация:

3.) Тест простоты Ферма

Простое число удовлетворяет тесту Ферма. Составной объект может пройти тест Ферма с вероятностью . Сложность разрядной операции испытания Ферма равна сложности алгоритма, который вычисляет возведение в степень.Поскольку вычисление (mod N) довольно быстрая операция, у нас возникает быстрый тест, проверяющий, является ли данное число составным. Его называют тестом Ферма по основанию а. Заметим, что тест Ферма может лишь убедить нас в том, что число N имеет делители, но не в состоянии доказать его простоту. Действительно, рассмотрим составное число N = 11 · 13 = 341, а основание в тесте Ферма выберем равным 2. Тогда = 1 mod 341, в то время как число 341 не простое. В этом случае говорят, что N — псевдопростое число (в смысле Ферма) по основанию 2. Существует бесконечно много псевдопростых чисел по фиксированному основанию, хотя они встречаются реже, чем простые. Можно показать, что для составного N вероятность неравенства
≠ 1 (mod N).
больше 1/2. Подводя итог сказанному, выпишем алгоритм теста Ферма.
Если на выходе этого алгоритма напечатано «составное, а», то мы с определенностью можем заявить, что число n не является простым, и что а свидетельствует об этом факте, т. е. чтобы убедиться в истинности высказывания, нам достаточно провести тест Ферма по основанию а. Такое а называют свидетелем того, что n составное.
Если же в результате работы теста мы получим сообщение: «правдоподобно простое», то можно заключить: n — составное с вероятностью ≤ существуют составные числа, относительно которых тест Ферма выдаст ответ правдоподобно простое, для всех взаимно простых с n оснований а. Такие числа называются числами Кармайкла. К сожалению, их бесконечно много. Первые из них — это 561, 1105 и 1729. Числа Кармайкла обладают следующими свойствами:

они нечетны,
имеют по крайней мере три простых делителя,
свободны от квадратов1,
если р делит число Кармайкла N, то р — 1 делит N — 1.

Чтобы получить представление об их распределении, посмотрим на числа, не превосходящие . Среди них окажется примерно 2, 7 • простых чисел, но только 246 683 ≈ 2,4 • чисел Кармайкла. Следовательно, они встречаются не очень часто, но и не настолько редко, чтобы их можно было игнорировать.

4.)Тест Миллера — Рабина

Вероятностный полиномиальный тест простоты. Тест Миллера — Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.
Алгоритм был разработан Гари Миллером в 1976 году и модифицирован Майклом Рабином в 1980 году.