[프로그래머스 | Lv. 1 | JavaScript] 소수 찾기

 

Link

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

 

---

문제

풀이

(1)

function solution(n) {
    let answer = 0;
    
    for (let i = 2; i <= n; i++) {
        let cnt = 0;
        const sqrt = Math.sqrt(i);
        for (let j = 1; j < sqrt; j++) {
            if (i % j === 0) cnt += 2;
        }
        if (i % sqrt === 0) cnt += 1;
        
        if (cnt === 2) answer += 1;
    }
    
    return answer;
}

(2)

function solution(n) {
    let primes = new Array(n + 1).fill(true);
    primes[0] = primes[1] = false; // 0과 1은 소수가 아님

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

    return primes.filter(v => v).length;
}

간단 해설

풀이(1) 은 타임아웃이 발생함. O(n 루트 n)

풀이(2) 는 에라토스테네스의 체 활용. O(n 로그 로그 n)

주의점

풀이(1) vs. 풀이(2) 제출 결과

풀이(1) vs. 풀이(2) 시간복잡도