[Programmers/JS] 약수의 개수와 덧셈

https://school.programmers.co.kr/learn/courses/30/lessons/77884

프로그래머스

 

1. 문제 풀이

• left에서 right까지의 수를 약수의 개수가 홀수, 짝수이냐에 따라서 answer에 연산을 하는 문제.
• 첫번째 반복문에서는 i가 left에서 right까지 순회할 수 있도록 설정한다.
• count 변수는 약수의 갯수를 셀 목적으로 선언하였고, 두 번째 반복문에서 i가 j에 대해서 나누어 떨어질 때 약수이므로 count를 1씩 더해준다.
• 두 번째 반복문이 끝나면 count의 홀,짝 유무에 따라 answer에 연산을 해준다.

 

• 아래는 더 효율적인 방법으로, 두 번째 반복문에서 j를 i까지 전체 순회하는 것이 아닌 제곱근 까지만 순회하여 준다.
• 약수의 성질에 따라 제곱근을 해서 자기 자신이 나오는 경우가 아니면 짝을 짓기 때문에 count += 2를 해준다.
• ex) 16의 경우 => [1,2,4,8,16] // 2에 해당할 경우 8이 있다는 것을 확정적으로 알기 때문에.

2. 제출 코드

function solution2(left, right) {
    let answer = 0;
    
    for(let i = left; i <= right; i++) {
        let count = 0;
        for(let j = 1; j <= i; j++) {
            if(i%j === 0) count++;
        }
        
        if(count%2 ===0) answer += i;
        else answer -= i;
    }
    return answer
}
/////////////////////////////////////////////////////////////////
function solution(left, right) {
    let answer = 0;
    
    for(let i = left; i <= right; i++) {
        
        let count = 0;
        //[16] [1,2,4,8,16]
        //[15] [1,3,5,15]
        for(let j = 1; j <= (i**0.5); j++) {
            if(j * j == i) count++;
            else if(i%j ==0) count += 2;
        }
        if(count%2 ===0) answer += i;
        else answer -= i;
    }
    return answer
}