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

풀이 [ 에라토스테네스의 체 ] 

  const sqrt=parseInt(Math.sqrt(n))

제곱근 사용

√4, √5, √8 , √11, √24

2, √5 , 2√2, √11, 2√2*√3

즉, n이라는 수가 주어졌을 때 루트를 씌워서 나눠지면 √n의 배수라는 뜻 -> 소수가 아님 

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

 

왜 n+1을 했고, 0~2 index는 false로 했는가?

배열의 index는 0부터 시작 모든 배열의 값을 소수라고 가정한 뒤

n=10일 때, [false,false,true,true,true,true,true,true,true,true,true] => [0,1,2,3,4,5,6,7,8,9,10]

0과1은 소수가 아니므로 false

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

 

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

i가 2일 때
j=i*i-> j=4
j+=i -> j=6,8,10으로 증가

arr[4] -> 숫자 4 (소수가 아님)
arr[6] -> 소수아님 이하 동일...

i가 3일 때
j=i*j => j=9
j+=i => j=12(x)불가

arr[9] -> 숫자 9 (소수 아님)

 

결과적으로 2의배수와 3의 배수를 찾아서 false로 만든것이다.

 

만약 n=100일 때는 sqrt가 10이므로

i=2 ->배열의 4,6,8,10.. 번째의 index는 false

i=3 -> 배열의 9,12(2에서 걸림).. 번째의 index는 false

i=4는 false

i=5 -> 배열의 25,30(3에서 걸림)... 번째의 index는 false

i=6은 false

i=7 -> 배열의 49,56(2에서 걸림).. false

i=8,9,10은 false

 

결과적으로 2의 배수, 3의 배수, 5의 배수, 7의 배수... 이런식으로 배수를 찾아 false로 바꾸는 루프를 돌 것이다.

 

최종 코드

 

function solution(n) {
  let count=0
  const sqrt=parseInt(Math.sqrt(n))
  const arr=Array(n+1).fill(true).fill(false,0,2)
  for(let i=2;i<=sqrt;i++){
    if(arr[i]){
      for (let j = i*i; j <= n; j+=i) {
        arr[j]=false
      }
    }
  }

  for (let i = 2; i < arr.length; i++) {
    if(arr[i]) count++
  }
  return count
}

[출처]

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4