[Programmers] 소수 찾기 / JavaScript

문제

---

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

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

 

코드

---

function solution(n) {
  let arr = Array(n + 1)
    .fill(true)
    .fill(false, 0, 2); //처음 두 요소만 false로 fill하기

  //2부터 n까지의 수 중에서(1은 이미 소수가 아님) 루트n 이하의 수들만 봐주면 됨
  for (let i = 2; i * i <= n; i++) {
    //각 i에 대한 배수들을 판단해 해당 수는 false로 만들기(소수가 아니므로)
    for (let j = i * i; j <= n; j += i) {
      arr[j] = false;
    }
  }
  return arr.filter((i) => i).length;
}

 

후기

---

• 프로그래머스 Level1문제의 '소수 만들기'문제에서 소수를 판별하는 법을 익혔기 때문에 쉽게 풀어서 제출했는데, 왠지 채점시간이 엄청 길어지더니 결국 시간초과가 뜨고, 효율성 테스트에서 탈락했다
• 다른 분들도 시간초과나 효율성 때문에 고난을 겪으신는 것 같았다. 찾아보니 '소수 만들기'문제와 달리 이 문제는 1부터 n까지의 수 중에서 소수가 몇 개인지 찾는 문제이기 때문에 (소수 만들기 문제는 숫자하나에대한 소수판별만 하면 됐다) n이 커지면 커질수록 나의 원래 코드는 비효율적일 수 밖에 없었다
• 그래서 찾아보니, 소수를 찾아내는 알고리즘으로 "에라토스테네스의 체"라는 공식이 있었다. 현재까지도 이 공식이 소수를 찾는 데 가장 효율적인 공식이라고 한다.
• 에라토스테네스의 체 : 쉽게 말해, 소수는 1과 자기자신으로만 나누어 떨어지는 수이다. 그렇다면, 어떤 배수는 소수가 아니라는 뜻이다. n까지의 수 중에서 배수들을 제외하면 소수가 된다는 것이다.
• https://themarketer.tistory.com/73 처음에 이론만 봤을 때는 이해가 잘 안돼서 이 분의 블로그를 보니 쉽게 이해가 됐다. 공식이 간단하기도 한데 정말 큰 효율성을 자랑하는 것같다.