[Develop/CodingTest] 프로그래머스 소수찾기 레벨1

프로그래머스 소수 찾기 레벨 1

저번 코딩 테스트 공부에 이어 조금씩 발전해 나가기 위해서 소수찾기 코딩 테스트를 연습해 봤다.

이번에도 자바스크립트로 코딩 테스트를 진행하였고 역시나 만족하지 못하는 결과를 얻었지만, 조금 씩

풀다 보면 자연스레 발전할 것이라 믿는다.

 

 

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

코딩테스트 연습 - 소수 찾기

 

대강 문제는 n를 주어지고 n의 범위 중에 소수의 개수를 찾는 문제였다. 문제는 아래와 같다.

문제풀이에는 다양한 방법이 존재하지만 기존에 스터디를 같이 진행하는 팀원들과 에라토스테네스의 체에 대하여 공부를 했었기 때문에 에라토스테네스의 체로 풀었다.
에라토스테네스의 체는 간단하게 말하면 1 ~ n까지의 수에서 n의 소수는 n의 제곱근까지의 배수를 모두 제외하면 n까지의 소수만 남게 된다.
예를 들어 1~100까지의 소수는 100은 10까지의 배수를 제외하면 된다. 따라서 2 3 5 7의 배수만 제외해주면 된다.
제곱근의 배수 제외 또한 전부 제외할 필요가 없다. 그 이유는 m = a * b 일 때 a와 b 중 하나는 n의 제곱근에 포함되기 때문이다.
n의 제곱근 보다 작은 합성수 m은 작은 a 나 b의 배수로 체크된다.

 

풀이는 먼저 n까지 크기의 배열을 만들고 0과 1은 소수가 아니기 때문에 false로 값을 채워준다. 2부터 시작하여 i * i <== 100 조건을 통해
제곱근까지의 배수만 제외할 수 있도록 했다.

다음 i의 값이 이미 소수의 배수들로 처리가 되어있는지 확인을 위해 arr[i] 조건을 줘 배수처리를 하지 않도록 한다.
다음은 j는 i * i부터 시작해 소수는 true 처리가 되도록하고 j+=i를 통해 배수들을 모두 제외했다.

 

마지막으로 소수만 남은 배열에서 filter 함수를 통해 값이 true 조건으로 배열을 뽑아 갯수를 반환하였다.

let solution = (n) => {
      // 0부터 시작임으로 배열의 크기를 1개 늘려준다.
    let arr = Array(n+1).fill(true).fill(false, 0, 2);

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

    return arr.filter(isPrime => isPrime).length;
}