[TIL-001] 알고리즘 - 에라토스테네스의 체(소수를 구하는 방법)

Today목표 : 4/10일 Challenge 11개 문제  풀기 ✅

---

알게된 점,

1. 진법 전환 방법

1. 10진법을 3진법으로 변환 => toString()을 이용

string.toString(3)

2. 3진법을 10진법으로 변환 => parseInt()를 이용

parseInt(string,3)

프로그래머스

 

 

2. 에라토스테네스의 체(소수를 구하는 방법)

요구사항

: 배열 중에서 3개의 수를 뽑아 더하는 모든 경우의 수 중에서, 소수가 되는 경우의 개수를 구하라

문제사항

1. 배열에서 3자리 수를 뽑아 더해서 만들 수 있는 모든 경우의 수를 구해야 한다.

먼저 구해야하는 숫자가  3자리 이기 때문에, 중첩 for문을 3번 반복 순환하여 배열에서 3자리 숫자를 인덱스로 뽑고자 하였다. 하지만 여기서 모든 인덱스를 다 돌려면 시간복잡도가 배열의 길이가 길어질수록 오래걸리기 때문에 이를 줄이기 위한 방법이 필요했다.  

let arr = []
    for(let a = 0; a < nums.length; a++){
        for(let b = a+1; b < nums.length; b++){
            for(let c = b+1; c < nums.length; c++){
               arr.push(nums[a] + nums[b] + nums[c])
            }
        }
    }

숫자 조합의 규칙을 살펴보니 더해지는 숫자의 조합이 중복되는 경우는(1+2+3과 1+3+2는 합이 같다.) 세자리 수의 합이 같기 때문에, 첫번째 숫자와 두번째, 세번째 숫자가 중복되는 인덱스부터 구하지 않도록 앞 숫자 인덱스 숫자+1 해주어 구하니 중복되는 경우를 훨씬 줄일 수 있었다.

 

2. 배열의 값들을 순환하며 소수인 수를 찾기

위에서 걸러진 숫자들로 이루어진 배열을 순환하며 소수인 수, 즉 1과 자신만을 약수로 가지는 수를 판별하기 위해 for문으로 순환하면서 숫자 2부터 자기자신-1까지를 나누어 약수가 없는 숫자만 선별하였다.

let primeNumber = 0
    for (let i = 0; i < arr.length; i++){
        let arr2 = []
        for (let j = 2; j < arr[i]; j++){
            if(arr[i] % j === 0){
                arr2.push(j)
            }
        }
        
        if(arr2.length===0){
            primeNumber++
        }
    }

문제는 이 또한 순환해야 하는 배열이나 숫자 범위가 클 수록 덜 하여 시간복잡도가 굉장히 오래걸린다는 것이다. 이를 줄일 수 있는 방법이 없을까 고민했다.

❗에라토스테스의 체라는 소수를 구하는 공식이 있었다. 에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘으로 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

JavaScript__에라토스테네스의 체 구현 - 개발꿈나무의 개발로그

코딩테스트 #14 소수 찾기 (에라토스테네스의 체)

결론적으로, n=100일 때, 100까지의 소수를 구하고 싶다면, 100의 제곱근인 2~10까지의 숫자에 대한 소수의 배수만 제외하면 100까지의 소수를 구할 수 있다는 것이다. 공식은 다음과 같이 참고하여 활용하도록 한다.

// 에라토스테네스의 체를 이용하여 2~n까지 소수 갯수 구하기
let solution = (n) => {
    let arr = Array(n+1).fill(true).fill(false, 0, 2);

    for(let i=2; i*i<=n; i++){
        if(arr[i]){
            for(let j=i*i; j<=n; j+=i){
                arr[j] = false;
            }
        }
    }

    return arr.filter(e => e).length;
}

그 밖에 제곱근을 사용하는 등 다른 방법도 있으므로 다음 번에 참고하면 좋을 것 같다.

 for (let i = 2; i <= Math.sqrt(num) ; i++) {
        if (num % i === 0) return false;
    }

[알고리즘] 소수 판별하기 - 여러가지 방법의 소수 판별법 by javascript

프로그래머스

 

그 밖에 알게된 점,

1. filter, map 등 에서도 val 뿐만 아니라, idx, arr를 활용할 수 있다.

2. 배열의 인덱스 순서를 활용하여 순서에 따른 값을 가져와 활용할 수 있다.

3. trim()의 공백 제거는 앞, 뒤만 가능하다. 따라서 사이의 공백들은 제거되지 않는다.