소수 찾기(Javascript)

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를 반환

나의 풀이

//소수 판별 -> 갯수 세기
function solution(n) {
    let prime = [];
    for (let i = 2; i <= n; i++){
        prime[i] = []
        for(let j = 2; j<= i; j++){
            if(i % j === 0)
            prime[i].push(j);
        }
    }
    return prime.filter(v => v.length === 1)
                .map(v => v[0])
                .length
  

처음에는 이런 식으로 풀었다. 2부터 1씩 증가시켜가면서, 검사할 수가 2면 2까지, 3이면 3까지 검사하면 되므로 j의 조건은 j<=i로 주었다.그리고 나누었을 때 나머지가 0인 수를 검사하였다. 숫자 하나를 검사할 때 마다 다른 배열에 담아 주었고, 그것을 다시 배열로 감싸 2차원 배열을 만들어 주었다. 2부터 시작해서 검사했으므로 소수는 자기자신 하나만을 배열의 인수로 가지고 있을 것이다. 따라서 길이가 1인 배열의 첫번째 인수를 인출한 다음, 그 숫자를 length로 세주었다.

검사 자체는 통과했는데 이번엔 효율성 테스트 시간이 빡빡했다. 숫자가 커지면 커질수록 비효율적이었기 때문이다. 그래서 소수의 특징을 찾아보니 에라토스테네스의 체라는 개념을 찾을 수 있었다. 에라토스테네스의 체는 n까지의 소수를 구할 때, 각 배수를 하나씩 지워나가는 것부터 시작한다. 2의배수, 3의배수, 5의 배수... 이런 식으로 제거하다보면 마지막엔 결국 소수만 남게 된다는 것이다. 이 때 √n보다 작은 소수로만 검사하면 결국 소수가 전부 걸러진다는 개념이다. 이 링크의 그림에 직관적으로 설명되어 있다.

그래서 에라토스테네스의 체에 맞게 다시 코드를 짰다.

function solution(n) {
    let prime = new Array(n).fill(1);
    prime[0] = 0;
    for (let i = 2; i <= n; i++){
        if (prime[i-1])
        for(let j = i * i; j <= n; j += i){
           prime[j-1] = 0;
        }
    }
    return prime.filter(v=>v === 1).length;
}

맨 처음에 새 배열을 만들어 전부 n만큼의 1로 채워 준다. 1은 소수라는 뜻이고 0은 소수가 아니라는 뜻이다. 1은 무조건 소수가 아니므로 0으로 미리 넣어 준다. 그리고 2부터 n까지 반복해서 검사하는데, 배열의 i-1자리가 1(참)이라면 그의 배수를 지워 준다. i * i이전의 값은 이미 검사 되었으므로 i * i를 초기값으로 주고, j가 n보다 작을 때까지 검사한다. 그리고 i의 배수를 삭제해줘야 하기 때문에 j는 i씩 증가한다.

이렇게 검사하면 결국 소수는 1, 소수가 아닌 수는 0이 된다. 1을 전부 filter해서 길이를 재 주면 소수의 개수가 나오는 것이다.