[프로그래머스][LEVEL1] 소수 찾기

# 문제 원문

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

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

제한 조건

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

입출력 예

n / result

10	4
5	3

입출력 예 설명

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

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

# 문제 풀이

소수에 대한 수학적 지식을 망각한지 확인하는 문제, 단순히 모든 수를 2부터 반복해서 체크하면 정확도는 몰라도 효율성에서 통과를 하지 못한다. 결국 한번에 모든 소수를 구한 후에 그 result를 체크해야한다.

다행히 소수라는 것은 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수(1 제외) 라는 개념이니 해당 소수의 배가 되는 수들은 소수가 될 수 없다는 규칙을 가진다.

그러니 2부터 2+2+n이 되는 수들을 모두 제하면서 전체 소수들을 구한후 그 갯수를 반환 해주면 된다.

 

# 솔루션 플로우

1. 입력 받은 n보다 1큰 배열(n + 1, 편의성)을 만들고 모든 요소를 true로 채운다.

2. 가장 작은 소수인 2부터 시작해서 반복하면서 입력받은 n의 *까지 result의 요소가 true인지 확인한다.

3. true일 경우 해당 수의 2배수 부터 n의 범위까지 계속 2,3,4,5,n배수를 false로 바꿔나간다.(해당 수들은 해당 num으로 나누어지니 소수가 아니다.)

4. 그렇게 얻어진 result를 필터링해서 true만 남긴다.

5. 그렇게 구해진 result의 length에서 소수가 아닌 0과 1의 만큼 빼고 반환해준다. (result.length - 2);

1. 에라토네스의 체를 이용한 풀이

function solution(n) {
    const result = new Array(n + 1).fill(true);

    for (let num = 2; (num * num) <= n; num++) {
        if (result[num]) {
            for (let int = (num * 2); int <= n; int += num) {
                result[int] = false;
            }
        }
    }

    return (result.filter((prime) => prime !== false).length - 2);
}