모든 챌린지
쉬움 0명 해결 정답률 0%

진약수의 합

n보다 작은 n의 약수를 모두 더합니다.

배우게 될 내용

  • 약수를 짝으로 찾을 수 있다
  • 반복을 제곱근에서 멈출 수 있다
  • 제곱근인 약수를 두 번 세지 않을 수 있다

문제

원문 보기 (영어)

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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.