[프로그래머스] 약수의 개수와 합

약수의 개수와 합 문제 설명

이번 문제는 프로그래머스 1단계 - 약수의 개수와 합 문제입니다.

사실 단순하게 풀자면 저처럼 푸는 것이 가장 단순할 것 같은데요. 

다만 이러한 방식은 O(n^2)이 되기 때문에 퍼포먼스에서 좋지 않을 것 같습니다. 

function solution(left, right) {
    let result = 0;
    for (let i = left; i <= right; i++) {
        let isEven = true;
        for (let j = 1; j <= i; j ++) {
            if (i % j == 0) isEven = !isEven;
        }
        result += isEven ? i : i * -1;
    }
    return result;
}

 

그래서 문제를 풀이한 이후, 다른 분들의 정답 또한 참고해보았는데요.

제곱근이 정수면, 약수의 갯수가 홀수라는 공식을 사용해 푸셨습니다. 정말 대단하십니다.

이렇게 풀이하면 O(n)이 되겠습니다. 훨씬 좋군요. 오늘도 한 수 배워갑니다.

 

피드백은 언제든지 환영이니 잘못된 부분이나, 문제가 있다면 댓글 꼭 부탁드립니다.

감사합니다.