[프로그래머스] Lv1) 기사단원의 무기 ( 에라토스테네스의 체, 소수 , 약수 찾기 )

이 문제는 약수 찾기의 문제입니다

function solution(number, limit, power) {
    let arr = []
    let count = 0
    for(let i = 1; i <= number; i++) {
        for(let j = 1; j <= i ; j ++){
            if(i % j === 0 ) count++
        }
        arr.push(count)
        count = 0
    }
    return  arr.map(e => e > limit ? power : e).reduce((a,b) => a+b);
}

이 코드는 시간복잡도가 O(n^2)이기에 시간초과로 fail 이 된 경우 입니다.

시간 복잡도를 줄이기 위해서는 에라토스테네스의 체를 이용해야한는 것을 검색을 통해 힌트를 얻었습니다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

일단 에라토스테네스의 체를 이해하려면 다음을 이해해야 합니다.

 

1. 약수의 대칭성:
   어떤 수 n의 약수들은 항상 쌍을 이룹니다.
   만약 a가 n의 약수라면, n/a도 n의 약수입니다.
   예: 12의 약수는 1, 2, 3, 4, 6, 12입니다. (1,12), (2,6), (3,4)가 쌍을 이룹니다.
   
   
2. 제곱근까지만 검사하면 되는 이유:
   n의 제곱근보다 큰 약수는 항상 n의 제곱근보다 작은 약수와 쌍을 이룹니다.
   따라서 제곱근까지만 검사하면 모든 약수 쌍을 찾을 수 있습니다.
   
   
3. 7의 경우:
   7의 제곱근은 약 2.65입니다.
   따라서 2와 3까지만 검사하면 충분합니다.
   4, 5, 6은 7의 제곱근보다 크므로 검사할 필요가 없습니다.
   
   
4. 왜 4, 5, 6으로 나누는 연산이 불필요한가:
   만약 7이 4, 5, 또는 6으로 나누어 떨어진다면, 반드시 그보다 작은 수(2 또는 3)로도 나누어 떨어져야 합니다.
   예를 들어, 만약 7이 4로 나누어 떨어진다면, 2로도 나누어 떨어져야 합니다.
   하지만 우리는 이미 2로 나누어 떨어지지 않는다는 것을 알고 있습니다.
   
   
5. 일반화:
   n이 어떤 수 x로 나누어 떨어진다면, n은 반드시 x의 약수들로도 나누어 떨어집니다.
   따라서 n의 제곱근까지만 검사하면, 그 이상의 수로 나누어 떨어지는지 여부를 이미 알 수 있습니다.

function solution(number, limit, power) {
    function countDivisors(n) {
        let count = 0;
        for (let i = 1; i * i <= n; i++) { // n의 제곱근까지만 반복합니다.
            if (n % i === 0) { // i가 n의 약수인지 확인합니다
                count += (i * i === n) ? 1 : 2; //  i * i === n인 경우 ( i가 n의 제곱근인 경우), 약수는 하나만 추가됩니다.
	                     // 그렇지 않은 경우, i와 n/i 두 개의 약수가 추가되므로 2를 더합니다.
            }
            if (count > limit) return power;
        }
        return count;
    }

    let totalPower = 0;
    for (let i = 1; i <= number; i++) {
        totalPower += countDivisors(i);
    }
    return totalPower;
}

 

이렇게 제곱근 까지만 계산하면 시간 초과 없이 통과할 수 있습니다

 

그리고 소수 , 약수, 배수, 소인수분해, 최대공약수  찾기 등의 문제에서 활용할 수 있으므로 

반드시 익혀야할 원리입니다.