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 패턴 프로그램

목차

파이썬 프로그램

완전수를 찾기 위한 기본 솔루션은 2를 숫자-1로 반복하고, 적절한 약수의 합을 유지하고, 합이 숫자와 같은지 확인하는 것입니다.

n=int(input("숫자를 입력하세요"))
합계=1
범위(2,n)의 i에 대해:
if(n%i==0):
합계=합+나
if(합==n):
print(n,"완벽한 숫자입니다")
또 다른:
print(n,"완전한 숫자가 아닙니다")

코드를 살펴보겠습니다.

기본적으로 사용자 입력은 파이썬에서 문자열로 읽히기 때문에 우리는 먼저 사용자 입력으로 n을 초기화하고 정수로 형변환합니다. n이 완전수인지 아닌지 확인해야 합니다. 루프에서 반복을 제외하고 2에서 직접 시작할 수 있도록 1은 모든 정수(0 제외)에 대한 적절한 제수이기 때문에 합계를 1로 초기화한다는 점에 유의하십시오.

2를 number-1로 반복하고 합이 적절한 제수이면 정수를 합에 더합니다. 마지막으로 루프에서 나올 때 얻은 합계가 숫자와 같은지 여부를 확인합니다. 조각 케이크 맞죠?

약간 최적화된 버전

위의 프로그램을 테스트한 후 최적화할 수 있는지에 대한 질문이 있을 수 있습니다. 하지만 알고리즘을 변경하지 않고 반복 횟수를 number/2로 줄일 수 있습니다. 숫자는 number/2보다 큰 적절한 약수를 가질 수 없다는 아이디어를 얻었기 때문입니다.

n=int(input("숫자를 입력하세요"))
합계=1
범위(2,n//2+1)의 i에 대해:
if(n%i==0):
합계=합+나
if(합==n):
print(n,"완벽한 숫자입니다")
또 다른:
print(n, "완전한 숫자가 아닙니다")

위의 스니펫은 number/2까지 반복한다는 점만 제외하면 이전 스니펫과 거의 유사합니다. float 유형으로 변환하는 것을 피하기 위해 정수 나누기를 수행하고 있으며 범위의 마지막 정수가 파이썬 루프에서 고려되지 않기 때문에 n//2+1까지 반복한다는 점에 유의하십시오.

제한 사항

주어진 범위에서 완전한 숫자를 찾도록 요청받을 때 우리의 솔루션은 number^2, 즉 O(n²) 시간 복잡도에 비례하는 시간을 소비합니다. 주어진 범위의 각 숫자를 반복한 다음 각 숫자에 대한 적절한 제수를 확인해야 하기 때문입니다. 그리고 완전수 조건을 만족하는 수는 거의 없습니다. 예를 들어, 0에서 1000 사이의 완전수의 수는 3(6, 28, 496)에 불과합니다.

적절한 제수를 찾기 위해 모든 요소를 ​​반복할 필요가 없는 최적화된 솔루션이 있습니다. 유클리드의 공식에 따르면 2 n −1(2 n − 1)은 2 n −1(2 n − 1)이 모두 n, (2 n − 1)인 짝수 완전수입니다. 소수. 예를 들어, 6은 n이 2이고 2, 2 2 − 1(2 2 − 1 = 3)이 모두 소수인 위의 방정식을 충족합니다. 그러나 홀수 완전수가 있는지 묻는 질문에는 대답할 수 없습니다.

또한 모든 언어에는 저장할 수 있는 정수 범위에 제한이 있다는 것을 알고 있습니다. 이 제한으로 인해 가장 큰 완전수를 찾는 방법이 없을 수 있습니다.

이러한 모든 제한 사항은 입력 수가 크면 직면하지만 입력 수가 작으면 초기 솔루션이 더 짧은 시간에 작동합니다.

더 읽어보기: 웹 개발을 위한 Python 프레임워크

결론

우리는 정의를 알고 완전수의 개념을 이해했습니다. 숫자 찾기에 대한 기본 솔루션을 통해 걸었습니다. 완벽한 숫자인지 아닌지. 그리고 초기 솔루션을 살펴본 후 반복 횟수를 줄여 약간 최적화했습니다. 우리는 알고리즘의 한계를 극복하고 짝수 완전수를 찾는 유클리드 공식에 대해 논의했습니다.

이제 숫자가 완전수인지 아닌지를 확인하는 파이썬 프로그램을 알게 되었습니다. 코드를 직접 작성하고 중복되는 반복이 발견되면 최적화를 시도하십시오. 또한 주어진 숫자 범위에서 완전한 숫자를 찾는 코드를 작성해 보십시오.

python, 데이터 과학에 대해 자세히 알아보려면 작업 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크샵, 업계 전문가와의 멘토링을 제공하는 IIIT-B & upGrad의 데이터 과학 이그 제 큐 티브 PG 프로그램을 확인하십시오. , 업계 멘토와 1:1, 최고의 기업과 400시간 이상의 학습 및 취업 지원.

파이썬에서 완전수 프로그램의 복잡성을 설명하십시오.

어떤 수는 약수의 합과 같으면 완전수라고 합니다. 숫자가 완벽한지 확인하기 위해 두 가지 접근 방식이 있습니다. 첫 번째 접근 방식은 각 "i"에 대해 "j"번 반복하고 그 제수를 확인하기 때문에 시간 복잡도가 O(n2)인 순진한 접근 방식입니다.
두 번째 접근 방식은 시간 복잡도가 O(√n)인 최적화된 솔루션입니다. 여기서 우리는 모든 숫자를 반복할 필요가 없습니다. 다음과 같은 유클리드 공식을 사용하여 직접 결론을 내릴 수 있습니다.
2n−1(2n − 1), 여기서 n과 2n은 소수입니다.
그러나 이 공식은 홀수 완전수에는 적용되지 않으므로 다른 방법을 찾아야 합니다.

Perfect Number Program의 접근 방식의 한계는 무엇입니까?

이 두 가지 접근 방식 모두 좋지만 어느 정도만 가능합니다. 어느 쪽도 일부 기술로 인해 완벽한 접근 방식으로 간주될 수 없습니다. 이러한 접근 방식의 한계는 다음과 같습니다.

1. 첫 번째 및 순진한 접근 방식은 많은 시간과 메모리를 소모하고 O(n2)의 시간 복잡도를 갖기 때문에 더 나쁩니다. 이는 중첩 루프를 사용하고 외부 루프의 모든 요소에 대해 내부 루프를 n번 반복하기 때문입니다. 이 접근 방식은 순진하며 더 큰 n 값에 대해 TLE를 제공하므로 권장되지 않습니다.
2. 그런 다음 O(√n)의 문제를 해결하는 최적화된 접근 방식이 있습니다. 홀수 완전수가 사용되지 않는 한 이것은 좋은 접근 방식입니다. 이 접근 방식은 짝수 완전수에만 적용되는 "짝수 완전수에 대한 유클리드 공식"을 기반으로 하기 때문에 홀수 완전수를 확인할 수 없습니다.

Python은 경쟁 프로그래밍에 적합합니까?

Python은 C/C++ 및 Java에서 발전했으며 연구 및 개발 목적에 가장 적합한 언어로 간주됩니다. 그러나 경쟁 프로그래밍의 경우 대부분의 프로그래밍 커뮤니티는 Python을 기피합니다. Python이 세 언어 중 가장 느린 이유는 다음과 같습니다.