[프로그래머스] Lv.1 소수 찾기 - JS

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	return
10	4
5	3

입출력 예 설명

입출력 예 #1

• 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

• 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

실패

function solution(n) {
    return Array(n)
        .fill(0)
        .map((_, i) => i + 1)
        .filter((v) => {
            if (v < 2) return false;

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

시간 초과

결과

풀이

function solution(n) {
    const arr = Array(n + 1)
        .fill(0)
        .map((_, i) => i >= 2);

    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (arr[i]) {
            for (let j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    return arr.filter((v) => v).length;
}

에라토스테네스의 체 알고리즘 사용
n까지의 수가 있으면 2부터 n의 제곱근 까지의 배수(본인 제외)를 다 지운다. 지운 후 남은 숫자들이 소수

결과

문제 출처 - 알고리즘