소수찾기

프로그래머스 코딩테스트 1단계

• 에라토스테네스의 체
• filter()

---

소스코드

function solution(n) {
    

    // 에라토스테네스의 체
    // 어차피 0, 1은 소수가 아님 0번째부터 2개를 false로 채우기
    let arr = Array(n+1).fill(true).fill(false,0,2);

    for(let i = 2; i*i <= n; i++){
        // arr[i]가 참이라면
        if(arr[i]){
            // 소수에서 2배수가 되는 요소들을 false로 변경
            for(let j=i*i; j<=n; j+=i){
                arr[j]  = false;
            }
        }
    }
    // arr안에 요소가 참인 조건만 걸러서 길이를 구해야함
    return arr.filter(item => item).length;
}

console.log( solution( 5 ) )

---

코드리뷰

그냥 생코딩했다가 효율성 검사에서 막혀서 찾아보다가 에라토스테네스의 체 관련한 알고리즘을 찾았다. 분명 고등학교 때 한 번쯤 보고 관련된것도 되게 많이 찾아봤을 텐데 역시 공부는 꾸준히 안하면 다 까먹나보다. 화가났다. 진짜로 많이 났다.

에라토스테네스의 체 알고리즘의 기본 원리는 "n까지의 숫자들 중에서 소수를 찾고싶을 때, 소수의 배수는 소수가 될 수 없으니 제거한다"에서부터 시작한다.
예를들어 50까지의 수 중에서 2가 소수인데, 2를 제외하고 4,6,8,10,...은 소수가 될 수 없다는 것이다.

let arr = Array(n+1).fill(true).fill(false,0,2);

일단 숫자보다 하나 더 많게 배열을 생성하고 0번째부터 2개(0,1)은 소수가 아니니 false로 미리 지정해놓는다.

for(let i = 2; i*i <= n; i++)

2부터 n의 제곱근까지 for문을 돌린다.
소수를 구할 때 제곱근까지 범위를 지정해주면 조사하는 범위를 절반이나 줄여줘서 효율성있는 코드가 된단다. 암튼 그렇다고 한다,,,

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

만약 arr[i]가 참이라면 i의 배수들을 다 false로 바꿔준다.
에라토스테네스의 체 법칙에 따라 소거한다.

return arr.filter(item => item).length;

filter함수는 배열에서 특정 조건에 맞는 것들을 걸러서 반환해주는 함수이다. 여기서는 아이템이 true인것들만 반환해준 뒤에 길이를 체크해주면 된다.