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

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

입출력 예시

s	return
10	4
5	3

문제풀이

해당 문제는 ‘에라토스테네스의 체’를 이용하여 풀어야 한다.
그 이유는 시간복잡도를 √n으로 해결할 수 있기 때문이다.
에라토스테네스의 체는 다음과 같은 그림으로 설명이 가능하다.

출처: 나무위키 1을 제외한 2부터 시작해 소수는 표시를 하지 않고, 배수(합성수)만 지워준다.

해당 문제는 개념을 이해하는 데 중점을 두었다.
풀이는 다양한 블로그를 통해 이해한 뒤 가장 이해가 잘 되는 풀이를 손으로 풀고 문제를 푸는 방식으로 진행하였다.

나의 풀이

function solution(n) {
    let newArr = new Array(n).fill(1);
    newArr[0] = 0;

    //제곱근 순회 
    for(let i = 2; i*i <= n ; i++) {
        //증감문으로 배수를 순회
        for(let j = i*i ; j <= n; j+=i){
            newArr[j-1] = 0;
        }
    }
    return newArr.filter((el)=> el===1).length
}

1) n개의 개수만큼의 배열에 ‘1’을 채운다.
2) 1이 들어간 배열의 0번째 자리에 ‘0’을 넣는다.
3) 제곱근 순회를 하게끔 만든다
4) for에서 증감문을 이용하여 배수를 순회할 수 있도록 만든다.
5) 제곱근 순회와 배수 순회를 통해 해당하는 인덱스 자리에 ‘0’을 넣는다.
6) Array.filter()메서드를 사용하여 내용이 ‘1’과 같은 배열을 filter한 뒤 그 길이를 반환한다.

도움되는 자료

https://ko.khanacademy.org/computing/computer-science/cryptography/comp-number-theory/v/sieve-of-eratosthenes-prime-adventure-part-4