프로그래머스 Lv.1 약수의 합 (JavaScript)

자바스크립트로 프로그래머스 문제 풀기

문제

- 출처: https://school.programmers.co.kr/learn/courses/30/lessons/12928

입력받은 수의 약수의 합을 구하는 문제이다. 소수 찾기의 반대로 생각하면 된다.

소수찾기에 대한 내용은 다음 글에 정리하였다.

2022.09.03 - [자료구조&알고리즘/개념 및 이론] - 소수 구하기 (자바스크립트)

소수 구하기 (자바스크립트)

 

풀이

나의 풀이

function solution(n) {
    var answer = 0;
    if(n <= 1) return n;
    if(n === 2) return 3;

	//시간복잡도를 줄이기 위해 제곱근을 사용하였다.
    for(let i = 1; i <= parseInt(Math.sqrt(n)); i++) {

        if(n % i === 0) {
            if(i === Math.sqrt(n)) {
                answer += i //제곱근의 경우는 짝을 이루는 약수가 자기 자신이다.
            } else {
            answer += (i + (n / i))
                    console.log(i, n/i, answer)
            }
        }
    }
    return answer;
}

약수의 합은 결국 소수찾기와 연관되어 있는 문제이다. 시간복잡도를 줄이기 위해 제곱근을 사용하여 반복문을 실행하였다.

약수는 짝을 이루므로 하나의 약수만 찾으면 짝을 이루는 수를 구할 수 있고, 이를 같이 더하였다.

 

이 문제에서 주의할 점

- 입력값 0~2까지일때 처리방법

- 약수가 제곱근일 경우, 짝을 이루는 약수는 자기자신이다. 

   예) 16의 약수는 1, 2, 4, 8, 16 이다. 이때 제곱근인 4는 하나만 존재하기에 합을 계산할 때 한번만 계산되도록 한다.