항해 8일차 (에라토스테네스의 체)

항해 8일차
오늘도 알고리즘을 풀었다.
오늘 내용을

간략하게 보자면

이런 내용에 문제를 풀었는데 팀원과 풀면서 소수를 판별하는 방법인 에라토스테네스의 체에 대해서 알게 되었다.

에라토스테네스의 체란?

에라토스테네스의 체(Eratosthenes' sieve)는 소수(prime number)를 구하는 알고리즘 중 하나이다.
동작하는 방법은
1. 구하고자 하는 범위 내의 모든 수를 나열합니다.
2. 2부터 시작해서, 각각의 배수를 지워나가며 소수를 찾아냅니다.
3. 이 과정을 반복하면서 소수만 남기고 나머지 수들을 모두 지워나갑니다.

예시)
에라토스테네스의 체는 소수를 찾아내는 알고리즘입니다. 구하고자 하는 범위 내의 모든 수를 나열하고, 2부터 시작하여 각 수의 배수를 지워나가며 소수를 찾아냅니다. 이 과정을 반복하면서 소수만 남기고 나머지 수들을 모두 지워나가면 됩니다. 예를 들어, 2부터 30까지의 소수를 구하고자 한다면, 2부터 시작하여 2의 배수를 지우고, 3의 배수를 지우고, 5의 배수를 지우고, 7의 배수를 지우고, 11의 배수를 지우고, 13의 배수를 지우고, 17의 배수를 지우고, 19의 배수를 지우고, 23의 배수를 지우고, 29의 배수를 지워나가면 2부터 30까지의 소수인 2, 3, 5, 7, 11, 13, 17, 19, 23, 29가 남게 됩니다.

에라토스테네스의 체를 사용하여 푼 코드

function solution(nums) {
    let numBox = []
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++){
            for (let k = j + 1; k < nums.length; k++){
                numBox.push(nums[i] + nums[j] + nums[k])
            }
        }
    }

    function prime(num) { // 에라토스테네스의 체
        if (num === 1) return false  // 3.xx
        for (let i = 2; i < num ** 0.5 + 1; i++) {
            if (num % i === 0) {
                return false
            }
        }
        return true
    }

    return numBox.filter((ele)=>prime(ele)).length
}

알게 된점

에라토스테네스의 체를 사용하여 숫자들의 집합에서 소수를 찾는 방법을 알게 되었다. 소수를 사용하는 알고리즘이 나왔을 때 응용하여 풀 수 있는 능력이 생각 뿌듯했당.