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

문제

1부터 n 사이에 있는 소수의 개수를 구하기
https://school.programmers.co.kr/learn/courses/30/lessons/12921

성공한 풀이

에라토스테네스의 체

두 번의 실패를 겪고, 결국 구글링으로 힌트를 얻었다.
'에라토스테네스의 체'

위키백과를 참조하여 하나씩 구현해본다.

1. 2부터 n까지 모든 수의 배열

const arr = [...Array(n-1).keys()].map(v => v+2);

2. 자신을 제외한 배수를 모두 제거

for (let i = 2; i < Math.sqrt(n); i++) {
  if (arr[i-2] !== null) {
    for (let j = 2; i * j <= n; j++) {
      arr[i * j - 2] = null;
    }
  }
}

3. 소수 개수 출력!

return arr.filter(v => v !== null).length;

실패한 풀이

2부터 자신 전까지 나누어 떨어지는지 확인

• for 중첩 반복문과 if문 활용

function solution(n) {
    let cnt = 0;
    for (let i = 2; i <= n; i++) {
        for (let j = 2; j <= i; j++) {
            if (j === i) cnt++;
            if (i % j === 0) break;
        }
    }
    return cnt;
}

1은 소수가 아니므로 2부터 n까지 반복문을 돌렸다.
중첩 반복문으로 나누는 수가 자신과 같아지면 cnt++를 수행하고,
1과 자신 외의 숫자로 나누어 떨어지면 멈춘다.
정확성 테스트 10~12, 효율성 테스트를 시간 초과로 실패했다.

2부터 제곱근까지 나누어 떨어지는지 확인

function solution(n) {
    let cnt = 0;
    for (let i = 2; i <= n; i++) {
        cnt++;
        for (let j = 2; j <= Math.sqrt(i); j++) {
            if (i % j === 0) {
                cnt--;
                break;
            }
        }
    }
    return cnt;
}

어떤 수 X를 구하는 식은, "X / 약수 = 또 다른 약수" 다.
1 × 20
2 × 10
4 × 5
(제곤급 × 제곱근) (이 경우, 정수는 아니지만 이해를 위해 적었다)
5 × 4
10 × 2
20 × 1
따라서 제곱근까지의 정수를 나누었다.

시간이 개선되어 정확성 테스트에 통과했으나,
효율성 테스트에서 하나 빼고 모두 시간 초과했다.