Программа Perfect Number в Python: как проверить, является ли число совершенным или нет?
Опубликовано: 2021-01-29Введение
Число называется совершенным числом, если сумма его собственных делителей (не считая самого числа) равна этому числу.
Чтобы лучше понять, давайте рассмотрим пример, правильные делители 6 равны 1, 2, 3. Теперь сумма этих делителей равна 6 (1 + 2 + 3 = 6), поэтому 6 называется совершенным числом. . Тогда как, если мы рассмотрим другое число, например 12, правильными делителями 12 будут 1, 2, 3, 4, 6. Теперь сумма этих делителей не равна 12, поэтому 12 не является совершенным числом.
Программирование на Python относительно проще и увлекательнее по сравнению с другими языками из-за более простого синтаксиса и хорошей читабельности. Теперь, когда мы разобрались с концепцией совершенного числа, давайте напишем программу на Python, чтобы проверить, является ли число совершенным числом или нет. Давайте создадим код на Python для проверки того, является ли данный пользовательский ввод идеальным числом или нет, и исследуем удовольствие от кодирования с помощью Python. Взгляните на наши программы по науке о данных, если вы заинтересованы в получении опыта.
Читайте: Программы шаблонов Python
Оглавление
Программа Python
Основное решение для нахождения совершенного числа состоит в том, чтобы перебрать 2 в цикле до числа-1, сохранить сумму его правильных делителей и проверить, равна ли сумма этому числу.
| n=int(input("введите число")) сумма=1 для i в диапазоне (2, n): если(n%i==0): сумма=сумма+я если (сумма==n): print(n,"является совершенным числом") еще: print(n,"не идеальное число") |
Давайте пройдемся по коду.
Сначала мы инициализируем n пользовательским вводом и приводим его к целому числу, потому что по умолчанию пользовательский ввод читается как строка в python. Нам нужно проверить, является ли n совершенным числом или нет. Обратите внимание, что мы инициализируем сумму 1, потому что 1 является правильным делителем для всех целых чисел (за исключением нуля), так что мы можем исключить итерацию в цикле и сразу начать с 2.
Мы переходим от 2 к числу-1 и добавляем целые числа к сумме, если это правильный делитель. И, наконец, когда мы выходим из цикла, мы проверяем, равна ли полученная сумма числу или нет. Кусок пирога, верно?
Немного оптимизированная версия
После пробного запуска вышеуказанной программы у нас может возникнуть вопрос, можем ли мы ее оптимизировать? Хорошо, но мы можем уменьшить количество итераций до числа/2 без изменения алгоритма. Потому что мы поняли, что у числа не может быть правильного делителя больше, чем число/2.
| n=int(input("введите число")) сумма=1 для i в диапазоне (2,n//2+1): если(n%i==0): сумма=сумма+я если (сумма==n): print(n,"является совершенным числом") еще: print(n, «не идеальное число») |
Приведенный выше фрагмент почти аналогичен предыдущему, с той лишь разницей, что зацикливается до числа/2. Обратите внимание, что мы выполняем целочисленное деление, чтобы избежать преобразования его в тип с плавающей запятой, и мы зацикливаемся до n//2+1, потому что последнее целое число в диапазоне не учитывается в цикле Python.
Ограничения
Когда нас просят найти идеальные числа в заданном диапазоне, наше решение потребует времени, пропорционального числу ^ 2, т. е. временной сложности O(n²). Потому что нам нужно перебрать каждое число в заданном диапазоне, а затем проверить наличие правильных делителей для каждого числа. И лишь немногие числа удовлетворяют условию совершенных чисел. Например, число совершенных чисел в диапазоне от 0 до 1000 равно 3 (6, 28, 496).
Для этого существует оптимизированное решение, в котором нам не нужно перебирать все элементы, чтобы найти правильные делители. Формула Евклида утверждает, что 2 n −1 (2 n − 1) является четным совершенным числом, где оба n, (2 n − 1) равны простые числа. Например, 6 удовлетворяет приведенному выше уравнению с n как 2, а оба 2, 2 2 - 1 (2 2 - 1 = 3) являются простыми числами. Но мы не сможем ответить, если нас попросят найти, существуют ли нечетные совершенные числа.
Кроме того, мы знаем, что каждый язык имеет ограничение на диапазон целых чисел, которые он может хранить. С этим ограничением у нас может не быть способа найти наибольшее совершенное число.
Со всеми этими ограничениями сталкиваются, если наш входной номер большой, но если наш входной номер мал, то наше первоначальное решение будет работать за меньшее время.
Читайте также: Python Framework для веб-разработки
Заключение
Мы знали определение и понимали концепцию совершенного числа. Пройдено основное решение для нахождения числа, идеальное число или нет. И после просмотра исходного решения мы его немного оптимизировали, уменьшив количество итераций. Мы рассмотрели ограничения нашего алгоритма и обсудили формулу Евклида для нахождения четного совершенного числа.
Теперь, когда вы знакомы с программой на Python, которая проверяет, является ли число совершенным числом или нет. Попробуйте написать код самостоятельно и попробуйте оптимизировать его, если обнаружите какие-либо перекрывающиеся итерации. Кроме того, попробуйте создать код для поиска совершенных чисел в заданном диапазоне чисел.
Если вам интересно узнать о python и науке о данных, ознакомьтесь с программой Executive PG IIIT-B и upGrad по науке о данных, которая создана для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические практические семинары, наставничество с отраслевыми экспертами. , общение один на один с отраслевыми наставниками, более 400 часов обучения и помощь в трудоустройстве в ведущих фирмах.
Объясните сложности программы Perfect Number в Python.
Число называется совершенным, если оно равно сумме своих делителей. Чтобы проверить, является ли число идеальным или нет, у нас есть два подхода. Первый подход — это наивный подход, где временная сложность равна O(n2), поскольку мы итерируем «j» раз для каждого «i» и проверяем его делители.
Второй подход представляет собой оптимизированное решение, где временная сложность составляет O(√n). Здесь нам не нужно перебирать каждое число. Мы можем сделать прямой вывод, используя формулу Евклида:
2n−1(2n − 1), где n и 2n — простые числа.
Однако эта формула не работает для нечетных совершенных чисел, и, следовательно, мы должны найти для них другой подход.
Каковы ограничения подходов программы Perfect Number?
Оба эти подхода хороши, но только до некоторой степени. Ни один из них нельзя считать идеальным подходом из-за некоторых технических особенностей. Ограничения этих подходов следующие:
1. Первый и наивный подход хуже, потому что он потребляет много времени и памяти и имеет временную сложность O(n2). Это связано с тем, что мы используем вложенный цикл и повторяем внутренний цикл n раз для каждого элемента внешнего цикла. Этот подход наивен и дает TLE для больших значений n, поэтому не рекомендуется.
2. Тогда у нас есть оптимизированный подход, который решает задачу за O(√n). Это хороший подход, если только в игру не вступают нечетные совершенные числа. Мы не можем проверить наличие нечетных совершенных чисел с помощью этого подхода, поскольку он основан на «формуле Евклида для четных совершенных чисел», которая работает только для четных совершенных чисел.
Подходит ли Python для соревновательного программирования?
Python произошел от C/C++ и даже от Java и считается наиболее подходящим языком для исследований и разработок. Но когда дело доходит до соревновательного программирования, большинство программистов избегает Python. Причина в том, что Python является самым медленным из этих трех языков.