[Programmers] 약수의 합

Link: Lv1. 약수의 합

  • 문제 설명

자연수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

제한 사항
n은 0 이상 3000이하인 자연수입니다.

 

  • 문제 풀이

간단한 문제지만 중요한 기본 개념 이므로 한 번 정리해 둔다.

위키피디아의 약수 뜻에 따르면, 약수(約數, 영어divisor) 또는 인수(因數, 영어factor)는

어떤 정수를 나머지 없이 나눌 수 있는 정수를 원래의 정수에 대하여 이르는 말이다. 

이 약수를 구하는 방법은 1부터 √n 까지 나누어 떨어지는 수를 하면 된다.

√n 까지만 진행하는 이유는 n = a * b 로 생각해 보면 된다.

n = 16 일 경우를 한번 생각해 보자.

a 1 2 4 8 16
b 16 8 4 2 1

표와 같이 a = 4 를 넘어 서는 순간 나머지는 반복하게 된다.

여기서 4는 n = 16이므로 √n에 해당되는 수이다.

즉, 1부터 √n 까지 나누어 떨어졌을 때의 수와 나눈 몫이 16의 약수가 되는 것이다.

이 문제는 이 약수들을 모두 더하면 끝난다.

Source Code: sum_of_divisor.cpp

댓글 남기기