[알고리즘] 프로그래머스 소수 찾기

프로그래머스 문제 링크

My Solution / Try

• 이중 반복문을 돌며 소수를 찾을 때 마다 Count
• 실행시간 초과 / 성능을 높이는 방법에 대한 고민

function solution(n) {
    
    let sum = 0
    
    for (let i = 2; i <= n ; i++) {
        let count = 0
        for (let j=1; j<=n; j++) {
         if (i % j === 0) {
             count ++
         } 
        }
        count === 2 ? sum += 1 : sum = sum
    }
    return sum
}

Advanced Solution

• '에라토스테네스의 체'라는 소수를 찾는 방법 활용
• i 이후의 i 배수는 약수로 i를 가지고 있는 것이 되므로 i 이후의 i 배수에 대해 false
• false 인 i는 이미 소수가 아니므로 i의 배수 역시 소수가 아님 (검사필요 x)

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;
}

참고자료

에라토스테네스의 체 - wikipedia