Perfect Number
n의 진약수는 n 자체보다 작은 양의 약수입니다. 완전수는 자신의 진약수의 합과 같습니다. 예를 들어 6 = 1 + 2 + 3입니다. 양의 정수 n이 주어집니다. n이 완전수이면 true를 반환하고, 그렇지 않으면 false를 반환하세요.
함수
- ninteger
- 테스트할 양의 정수
- 반환값boolean
- n이 진약수의 합과 같으면 true, 그렇지 않으면 false
제약 조건
1 ≤ n ≤ 108
예제
- 입력
- n = 28
- 출력
- true
- 설명
28의 진약수는1,2,4,7,14입니다. 이 수들을 더하면28이 되므로28은 완전수입니다.
- 입력
- n = 12
- 출력
- false
- 설명
12의 진약수는1,2,3,4와6입니다. 이들을 더하면16이 되어12를 초과합니다.
- 입력
- n = 1
- 출력
- false
- 설명
1은 진약수가 전혀 없으므로 합은1이 아니라0입니다.
제출 시 숨은 테스트 +16개
후속 질문
모든 짝수 완전수는 2^(p-1) × (2^p-1) 형태이며, 여기서 2^p-1은 소수입니다. 각 수를 하나씩 검사하지 않고 이 공식을 사용해 10^8보다 작은 모든 완전수를 나열할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
28의 진약수를 적어 보세요.5이하의 수만 살펴본다면 그중 어떤 수를 찾을 수 있을까요?약수는 쌍을 이룹니다.
d가n을 나누면n / d도 나눕니다. 각 쌍의 원소 중 하나는√n이하입니다.합계를
1로 시작하고,n == 1이면false를 반환한 다음,d * d ≤ n인 동안d를2부터 반복하세요.d와n / d를 더하되, 둘이 같을 때는 한 번만 더하세요.
풀이
정의는 약수의 합을 구하라고 하며, 가장 단순한 반복문은 n / 2까지 모든 후보를 확인합니다. n = 10^8이면 5 × 10^7번의 나눗셈을 수행합니다. 약수는 곱해서 n이 되는 쌍으로 이루어지므로, √n까지만 검색하면서 각 쌍의 두 수를 모두 모을 수 있습니다. 이는 약 10^4번의 단계입니다.
모든 진약수를 더하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
정의를 따르세요. 1부터 시작해 모든 d를 확인하고, n % d == 0이면 누적 합계에 d를 더하세요. 마지막에는 합계를 n과 비교하세요. 28의 경우 반복문은 1, 2, 4, 7, 14를 찾아내며, 1 + 2 + 4 + 7 + 14 = 28입니다.
n / 2에서 멈춰도 됩니다. n 이외의 약수는 몫이 최소 2이므로, n의 절반을 초과할 수 없습니다. 이 범위는 n = 1인 경우도 처리합니다. 반복문은 0번 실행되고, 합계는 0으로 유지되며, 답은 false입니다.
범위를 절반으로 줄여도 증가율은 바뀌지 않습니다. n = 10^8인 경우 반복문은 여전히 5 × 10^7번 실행되며, 약수가 있든 없든 그 크기의 모든 입력에 대해 그렇게 실행됩니다.
알고리즘
total을0으로 설정합니다.d를1부터n / 2까지 반복합니다.n % d == 0이면d를total에 더합니다.total == n인지 반환합니다.
def isPerfect(n):
total = 0
# No proper divisor of n is larger than n / 2.
for d in range(1, n // 2 + 1):
if n % d == 0:
total += d
return total == n제곱근까지의 약수 쌍을 구하세요
핵심 아이디어
d가 n을 나누면 n / d도 n을 나눕니다. 28의 약수 쌍은 1 × 28, 2 × 14, 4 × 7입니다. 각 쌍에서 한 수는 √n 이하여야 합니다. 두 수가 모두 √n보다 크면 곱이 n보다 커지기 때문입니다. 따라서 √n까지 탐색하면 모든 쌍을 한 번씩 찾을 수 있고, 탐색하면서 두 수를 모두 더하면 됩니다.
두 가지 경우는 주의해야 합니다. 1 × n 쌍에는 n 자체가 포함되는데, 이는 진약수가 아닙니다. 따라서 합계는 1에서 시작하고 탐색은 2에서 시작하세요. 하지만 n = 1의 유일한 약수는 자기 자신이므로, 이 시작값은 n = 1에는 맞지 않습니다. 따라서 먼저 false를 반환하세요. 그리고 n이 제곱수이면 제곱근은 자기 자신과 짝을 이룹니다. 예를 들어 36의 경우 6 × 6에서 6을 두 번이 아니라 한 번만 더해야 합니다.
경계 조건은 d * d ≤ n으로 쓰세요. 이렇게 하면 정수 범위 안에서 계산할 수 있습니다. n = 10^8일 때 반복문은 d = 10^4에서 멈추므로, 5 × 10^7회 대신 약 10^4회 실행됩니다.
알고리즘
n == 1이면false를 반환합니다.total을1로,d를2로 설정합니다.d * d ≤ n인 동안:d가n을 나누면d를 더하고,n / d가d와 다르면n / d도 더합니다.- 다음
d로 이동합니다. total == n인지 반환합니다.
def isPerfect(n):
if n == 1:
return False
total = 1 # 1 divides every n > 1; n itself does not count
d = 2
while d * d <= n:
if n % d == 0:
total += d
partner = n // d
if partner != d: # a square root pairs with itself: add it once
total += partner
d += 1
return total == n
함정과 경계 사례
쌍을 이용하는 방법은 간단하며, 이 방법의 버그는 각각 합계를 정확히 약수 하나만큼 바꿉니다.
n자체를 셉니다.1 × n쌍은n을 더하므로, 모든 수의 합이n보다 큰 것처럼 보이게 됩니다. 합계를1에서 시작하고 탐색은2부터 시작하세요.1을 완전수로 판정합니다. 합계를1에서 시작하면 입력값이1일 때1 == 1이 됩니다. 진약수의 합은0이므로, 반복문 전에 이 경우를 처리하세요.- 제곱근을 두 번 더합니다.
16의 진약수는1,2,4,8이며, 합은15입니다.4를 두 번 더하면19가 됩니다. d * d < n에서 멈춥니다. 그러면 제곱근을 완전히 건너뛰므로16의4를 세지 않습니다.- 부동 소수점 제곱근으로 상한을 정합니다. 단정밀도에서는, 또는 배정밀도에서
2^53을 초과하는 경우에는 완전제곱수의 제곱근이 실제보다 1 작게 나와 약수 하나를 놓칠 수 있습니다.d * d ≤ n검사는 정수만 사용하므로 이런 문제가 절대 발생하지 않습니다.
자주 묻는 질문4
완전수를 확인하는 시간 복잡도는 얼마인가요?
√n까지의 약수 쌍을 구하는 데는 O(√n) 시간이 걸리고 O(1) 공간을 사용합니다. n = 10^8일 때 약 10^4번의 단계가 필요합니다. n / 2까지 모든 후보를 검사하는 것은 O(n)이며, 같은 입력에 대해 약 5 × 10^7번의 단계가 필요합니다.
10^8 미만의 완전수는 몇 개입니까?
다섯 개입니다: 6, 28, 496, 8128 및 33550336. 빠르게 드물어집니다. 다음 수인 8589869056은 32비트 정수에도 들어가지 않습니다.
홀수 완전수가 있나요?
아무도 모릅니다. 지금까지 발견된 모든 완전수는 짝수입니다. 탐색을 통해 10^1500보다 작은 홀수 완전수는 존재하지 않는 것으로 밝혀졌지만, 홀수 완전수가 존재할 수 없다는 증명은 없습니다. 함수는 입력이 짝수라는 추측이 아니라 정의에 따라 작동해야 합니다.
완전수, 과잉수, 부족수의 차이는 무엇인가요?
진약수의 합을 해당 수와 비교하세요. 같으면 28처럼 완전수입니다. 더 크면 약수가 16으로 합산되는 12처럼 과잉수입니다. 더 작으면 모든 소수처럼 부족수입니다. 소수의 유일한 진약수는 1입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def isPerfect(n):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
n = 28
기대값
true