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

풀이 과정

그냥 무작정 구하면 효율성 테스트 통과를 못해서 별별 거 다 시도하다가 결국 질문하기에 있는 다른 사람의 힌트 보고 풀었다.

• 수에는 다음과 같은 성질이 있다고 한다.
  1. 1보다 큰 모든 자연수는 소수의 곱으로 이루어져 있다. (소인수분해..!)
     👉 자기보다 작은 소수로만 나누어 보면 됨
  2. 어떤 자연수가 있을때 그 수의 제곱근보다 작은 모든 소수들로 나누어 떨어지지 않으면 그 수는 소수다. (그 이상의 수는 어차피 작은 소수들을 곱한 수일 테니..)
     👉 범위가 제곱근보다 작은 소수가 되어서 1보다 더 적은 경우의 수
• 2번 방법이 효율적이니까 그 방법으로 풀면 된다.
  1. primes 배열에 지금까지 찾은 소수를 저장해 둔다.
     주어지는 수가 2 이상이기 때문에 일단 2를 저장해두고 결과에도 1을 미리 카운트 해둠
  2. 3부터 n까지 증가시키면서 소수인지 판별: 첫 번째 for
  3. primes 배열의 각 요소를 꺼내면서 지금 확인하는 수 i의 제곱근보다 작은 소수로 나누어떨어지는지 확인: 두 번째 for
  • 나누어떨어지면 소수가 아니므로 break
  • 꺼낸 소수가 제곱근보다 커졌으면 소수이므로 result를 증가시키고 primes 배열에 추가한 후 반복문 종료: push(), break

코드

function solution(n) {
  let result = 1;
  const primes = [2];
  for (let i = 3; i <= n; ++i) {
    for (const prime of primes) {
      if (i % prime === 0) break;
      if (prime > Math.sqrt(i)) {
        ++result;
        primes.push(i);
        break;
      }
    }
  }
  return result;
}

🤔

유명한 방식은 에라토스테네스의 체라고 하는데 일단 이렇게 풀어서 그냥 넘어간다...
너무 많은 시간을 썼음... 다음에 비슷한 문제가 나오면 알아보기로...