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

Проверьте, является ли число простым в Python

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

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

Используйте простой метод итерации для определения простого числа в Python

В этом методе мы используем простой метод итерации с использованием цикла for или while . Переберите числа, начиная с 2 и далее до K/2 , и проверьте, делит ли какое-либо из этих чисел K .

Если найдено число, соответствующее этому критерию, то возвращается False . С другой стороны, если все числа не соответствуют этому критерию, данное число K является простым числом, и возвращается значение True .

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

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

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

Как проверить, является ли число простым в Python

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

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

В этом уроке вы:

повторить основы простых чисел,
написать код Python, чтобы проверить, является ли число простым, и
оптимизируйте его дальше, чтобы получить алгоритм времени выполнения O (√ n).

Для всего этого и многого другого, давайте начнем.

Что такое простое число?

Начнем с рассмотрения основ простых чисел.

В теории чисел натуральное число n называется основной если у него ровно два делителя: 1 и само число (n). Вспомните из школьной математики: говорят, что число i является делителем числа n, если i делит n без остатка. ✅

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

nFactorsIs Prime?11Нет21, 2Да31, 3Да41, 2, 4Нет71, 7Да151, 3, 5, 15Нет

Из приведенной выше таблицы мы можем записать следующее:

2 — наименьшее простое число.
1 является множителем каждого числа.
Каждое число n само по себе является множителем.

Итак, 1 и n — тривиальные множители для любого числа n. И у простого числа не должно быть других делителей, кроме этих двух.

Это означает, что при переходе от 2 к n – 1 вы не сможете найти нетривиальный множитель, который делит n без остатка.

Алгоритм O (n) для проверки того, является ли число простым в Python

В этом разделе давайте формализуем описанный выше подход в виде функции Python.

Вы можете перебрать все числа от 2 до n – 1, используя объект range() в Python.

В Python range(start, stop, step) возвращает объект диапазона. Затем вы можете выполнить итерацию по объекту диапазона, чтобы получить последовательность от начала до конца -1 с шагом шага.

Поскольку нам нужен набор целых чисел от 2 до n-1, мы можем указать диапазон (2, n) и использовать его вместе с циклом for.

Вот что мы хотели бы сделать:

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

Если вы перебрали весь диапазон чисел от 2 до n – 1 и не нашли числа, которое делит n без остатка, то это число простое.

Функция Python для проверки простого числа

Используя вышеизложенное, мы можем пойти дальше и определить функцию is_prime() следующим образом.

Давайте теперь разберем приведенное выше определение функции.

Приведенная выше функция is_prime() принимает в качестве аргумента положительное целое число n.
Если вы найдете множитель в указанном диапазоне (2, n-1), функция вернет False, так как число не является простым.
И он возвращает True, если вы проходите весь цикл, не найдя множителя.

Далее давайте вызовем функцию с аргументами и проверим правильность вывода.

В приведенном выше выводе вы видите, что 2 и 11 — простые числа (функция возвращает True). И 8, и 9 не простые (функция возвращает False).

Как оптимизировать функцию Python is_prime()

Мы можем сделать небольшую оптимизацию здесь. Обратите внимание на список факторов в таблице ниже.

NumberFactors61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18

Итак, мы видим, что единственный множитель n, который больше n/2, — это сам n.

Таким образом, это означает, что вам не нужно зацикливаться до n – 1. Вместо этого вы можете запускать цикл только до n/2.

Если вы не найдете нетривиальный множитель до n/2, вы не сможете найти и множитель выше n/2.

Теперь давайте изменим функцию is_prime() для проверки факторов в диапазоне (2, n/2)

Давайте продолжим и проверим вывод с помощью нескольких вызовов функций.

Хотя может показаться, что мы оптимизировали, этот алгоритм не эффективнее предыдущего с точки зрения сложности выполнения. На самом деле, они оба имеют сложность выполнения O(n): пропорциональную значению n или линейную по n.

Можем ли мы сделать лучше? Да мы можем!

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

Алгоритм O(√n) для проверки простого числа в Python

Бывает, что множители числа встречаются парами.

Если a — фактор числа n, то также существует фактор b такой, что axb = n, или просто ab = n.

Давайте проверим это на примере.

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

Также обратите внимание, что √18 примерно равно 4,24.

А среди множителей, встречающихся парами (а, b), видно, что если а меньше 4,24, то b больше 4,24 — в этом примере (2, 18) и (3, 6).

Факторы 18 в парах

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

Если число n является полным квадратом, вы будете иметь a = b = √n в качестве одного из множителей.

▶️ Посмотрите на множители 36 в таблице ниже. Поскольку 36 — полный квадрат, a = b = 6 — один из множителей. Для всех остальных пар факторов (a, b) выполняется a 6.

Факторы 36 в парах

Подводя итог, имеем следующее:

Каждое число n можно записать как n = axb
Если n — полный квадрат, то a = b = √n.
А если a √n.
В противном случае, если a > b, то a > √n и b Как изменить алгоритм is_prime() на O(√n)

Приступим к оптимизации функции для проверки простых чисел в Python.

Теперь давайте разберем приведенное выше определение функции:

Чтобы вычислить квадратный корень числа, давайте импортируем встроенный математический модуль Python и используем функцию math.sqrt().
Поскольку n не может быть идеальным квадратом, нам придется привести его к целому числу. Используйте int(var) для преобразования var в int.
Чтобы убедиться, что мы действительно проверяем до √n, мы добавляем плюс один, поскольку функция range() по умолчанию исключает конечную точку диапазона.

Ячейка кода ниже подтверждает, что наша функция is_prime() работает правильно.

В следующем разделе давайте создадим несколько простых графиков, чтобы визуально понять O (n) и O (√ n).

Визуальное сравнение O(n) и O(√n)

▶️ Запустите следующий фрагмент кода в выбранной вами среде ноутбука Jupyter.

В приведенном выше фрагменте показано, как можно построить кривые для n и √n для диапазона значений.

Мы используем функцию NumPy arange() для создания массива чисел.
Затем мы собираем значения n и √n до 20, но не включая их, в Панды DataFrame.
Далее мы строим с помощью линейный график моряка() функция.

Из графика ниже видно, что √n значительно меньше n.

Давайте теперь увеличим диапазон до 2000 и повторим те же шаги, что и выше.

Из приведенного выше графика можно сделать вывод, что алгоритм O(√n) работает значительно быстрее, когда вы проверяете, является ли большое число простым.

Вот быстрый пример: 2377 — простое число — проверьте это!��

В то время как подход O(n) требует порядка 2000 шагов, алгоритм O(√n) может помочь получить ответ всего за 49 шагов.✅

Вывод

⏳ И настало время подвести итоги.

Чтобы проверить, является ли число простым, наивный подход состоит в том, чтобы перебрать все числа в диапазоне (2, n-1). Если вы не найдете множитель, который делит n, то n — простое число.
Поскольку единственный множитель n, превышающий n/2, — это само n, вы можете работать только до n/2.
Оба вышеупомянутых подхода имеют временную сложность O (n).
Поскольку множители числа встречаются парами, вы можете работать только до √n. Этот алгоритм намного быстрее, чем O (n). И выигрыш заметен при проверке, является ли большое число простым или нет.

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

Name already in use

python_lessons / python_coursera / 4_week / 55_Проверка числа на простоту.py /

Go to file T
Go to line L
Go to definition R
Copy path
Copy permalink

Open with Desktop
View raw
Copy raw contents Copy raw contents

Copy raw contents

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

Проверка, является ли число простым числом в Python [duplicate]

Я написал следующий код, который должен проверить, является ли введенный номер простым числом или нет, но есть проблема, с которой я не мог пройти:

Если введенный номер не является простым числом, он отображает «не просто», как и предполагалось, но если число является простым числом, оно ничего не отображает. Не могли бы вы мне помочь?

8 ответов

Существует много эффективных способов проверки примитивности (и это не один из них). Но цикл, который вы написали, может быть кратко представлен в Python:

То есть, a является простым, если все числа между 2 и a (не включительно) дают ненулевой остаток при делении на a.

На самом деле я не думаю, что в этих ответах найдено наилучшее решение, поэтому я собираюсь опубликовать свое сообщение и объяснить, почему это лучше:

Примечание: требуется проверка n > 1 , так как 1 не является простым числом, и поэтому равно нулю и любой отрицательное число.

Описание

Я собираюсь дать вам немного информации об этой почти эзотерической одиночной строке кода, которая будет проверять простые числа:

Прежде всего, использование range() — действительно плохая идея, потому что он создаст список чисел, в котором используется много памяти. Использование xrange() лучше, потому что оно создает generator , который не использует память для работы, но генерирует каждое число «на лету». Кстати, это не лучшее решение: попытка вызвать xrange(n) для некоторого n таким образом, что n > 2 31 -1 (что является максимальным значением для C long) вызывает OverflowError . Поэтому лучший способ создать диапазон generator — использовать itertools :

Вам действительно не нужно доходить до n , если вы хотите проверить, является ли n простым числом. Вы можете значительно уменьшить тесты и проверить только от 2 до √(n) (квадратный корень от n ). Вот почему:

Найдем все делители n = 100 и перечислим их в таблице:

Вы легко заметите, что после квадратного корня из n все найденные делители на самом деле уже найдены. Например, 20 уже был найден с помощью 100/5 . Квадратный корень из числа — это точная средняя линия, где найденные делители начинают дублироваться. Поэтому , чтобы проверить, является ли число простым, вам нужно всего лишь проверить от 2 до sqrt(n) .

Почему sqrt(n)-1 тогда, а не только sqrt(n) ? Это потому, что второй аргумент, предоставляемый объекту itertools.islice , — это количество итераций, которые нужно выполнить. islice(count(a), b) останавливается после b итераций. Вот почему:

Функция all(. ) является тем же из следующего:

он буквально проверяет все числа в iterable , возвращая False , когда число оценивается как False (что означает только, если число равно нулю). Почему мы используем его тогда? Во-первых, нам не нужно использовать дополнительную индексную переменную (например, мы будем использовать цикл), кроме этого: только для того, чтобы сделать это, реальной потребности в ней нет, но она выглядит менее громоздким для работы только с одной строкой кода вместо нескольких вложенных строк.

Расширенная версия

Я включаю «распакованную» версию функции isPrime() , чтобы ее было легче понять и прочитать: