Проверьте, является ли число простым в Python
Простое число может быть изображено как натуральное число без других положительных делителей, кроме числа 1 и самого себя. Число 1 не учитывается в списке простых чисел.
В этом руководстве будут рассмотрены различные методы, которые вы можете использовать, чтобы проверить, является ли число простым.
Используйте простой метод итерации для определения простого числа в Python
В этом методе мы используем простой метод итерации с использованием цикла for или while . Переберите числа, начиная с 2 и далее до K/2 , и проверьте, делит ли какое-либо из этих чисел K .
Если найдено число, соответствующее этому критерию, то возвращается False . С другой стороны, если все числа не соответствуют этому критерию, данное число K является простым числом, и возвращается значение True .
В следующем коде используется метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Проверяйте, пока не будет достигнут корень данного числа, вместо проверки точного числа. Этот процесс в основном устраняет избыточность, которая возникает, когда больший множитель числа K кратен меньшему множителю, который уже был повторен.
В следующем коде используется оптимизированный метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Оптимизированный метод итерации делает его быстрее и эффективнее, чем простой метод итерации, примерно на 30%.
Используйте функцию sympy.isprime() , чтобы проверить, является ли данное число простым числом в Python
SymPy — это библиотека на Python, используемая для реализации символьной математики. Это упрощенная система компьютерной алгебры (CAS), которая содержит все основные функции. Для этого метода необходима установка этого модуля, и его можно загрузить, просто используя команду pip .
Как проверить, является ли число простым в 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, посвященным операциям со строками, где вы научитесь проверять, являются ли строки палиндромами, анаграммами и т. д.
Алгоритм нахождения простых чисел
Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.
Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.
Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
# Листинг 1 # вводим N n = input(«n python»># Листинг 2 n = input(«n python»># Листинг 3 n = input(«n python»># Листинг 4 from math import sqrt n = input(«n python»># Листинг 5 from math import sqrt n = input(«n python»># Листинг 6 from math import sqrt n = input(«n python»># Листинг 7 n = input(«n python»># Листинг 8 n = input(«n tm-article-presenter__meta»>
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
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