문제
n의 진약수는 n 자기 자신을 뺀 양의 약수입니다. 12의 진약수는 1, 2, 3, 4, 6입니다. 진약수의 합을 보면 그 수가 완전수인지, 과잉수인지, 부족수인지 알 수 있습니다. 약수는 d와 n / d처럼 짝을 이루므로 d는 n의 제곱근까지만 확인하면 됩니다.
sum_of_proper_divisors(n) 함수를 구현하세요.
입력
n: 양의 정수입니다.
출력
n보다 작은 n의 양의 약수를 모두 더한 값을 반환합니다. n = 1이면 진약수가 없으므로 0을 반환합니다.
제약 조건
1 ≤ n ≤ 10^12
예시
예시 1
입력:
n = 12
예상 출력:
expected = 16
입력:
long long n = 12;
예상 출력:
long long expected = 16;
입력:
long n = 12;
예상 출력:
long expected = 16;
설명
1 + 2 + 3 + 4 + 6 = 16입니다.
예시 2
입력:
n = 28
예상 출력:
expected = 28
입력:
long long n = 28;
예상 출력:
long long expected = 28;
입력:
long n = 28;
예상 출력:
long expected = 28;
설명
1 + 2 + 4 + 7 + 14 = 28이므로 28은 완전수입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
d가 n을 나누면 n / d도 n을 나눕니다.
힌트 2
d는 n의 제곱근까지만 시도하고, 각 짝의 두 수를 모두 더하세요.
힌트 3
n 자신은 빼고, n이 완전제곱수이면 제곱근은 한 번만 더하세요.
예상 복잡도
시간 O(sqrt n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.