[문제풀이 후기] 프로그래머스 #12921/#120846 - 소수 찾기/합성수 찾기

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

 

기본 상위 코드

const n = 10;

 

규칙

약수
- 숫자 N 에 대하여 i 가 약수면, N / i 도 약수
- i × i = N 인 경우, 모든 약수의 조합이 ( i, i ) 를 기준으로 대칭
=> 약수 i 의 최대값은 Math.sqrt(N)

에라토스테네스의 체
- 소수 찾기 알고리즘
- 2 부터 Math.sqrt(N) 까지의 숫자 i 에 대하여 i 배수를 모두 제거
- 최종적으로 남은 배열 = 소수

 

첫 번째 시도 (결과 : 실패)

 

접근 방식

1. 1 부터 n 까지의 배열 생성
2. 2 부터 Math.sqrt(n) 까지의 숫자 i 에 대하여 i 의 배수가 아닌 항목 필터링
3. 이전에 수행한 i 는 그대로 유지
4. 최종적으로 필터링된 배열의 길이 - 1 (1 은 소수가 아님)

let array = Array.from({ length: n }, (_, i) => i + 1);

for (let i = 2; i * i <= n; i++) {
  array = array.filter((value) => value % i !== 0 || value <= i);
}

return array.length - 1;

 

실패 원인 : 시간 초과

- 전체 배열을 순회하고 계속해서 새 배열을 생성하는 것이 시간 초과의 원인이 됨

---

두 번째 시도 (결과 : 성공)

 

접근 방식

1. 0 부터 n 까지의 boolean 배열 생성
  1-1. 기본값 : true (true : 소수)
  1-2. 0, 1 은 소수가 아니므로 false 처리

2. 2 부터 Math.sqrt(n) 까지의 숫자 i 에 대하여 반복
  2-1. array[i] 가 true 인 경우, i 의 배수 index 에 대하여 array[index] 를 모두 false 처리
  2-2. 이전 i 의 배수는 모두 처리되었기 때문에 i 의 배수 작업은 i * i 부터 수행

3. 최종적으로 true 인 요소 => 소수

const array = new Array(n + 1).fill(true);

array[0] = false;
array[1] = false;

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

return array.filter(Boolean).length;

 

효과

시간 복잡도 개선 : O(n^2) -> O(n log log n)
공간 복잡도 개선 : 추가 배열 생성 없이 단일 배열에서 수행

---

심화 - 합성수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/120846

 

접근 방식

1. 0 부터 n 까지의 boolean 배열 생성
  1-1. 기본값 : false (true: 합성수)
  1-2. 0 과 1은 기본적으로 false 처리 되었기 때문에 별도 작업 불필요

2. 2 부터 Math.sqrt(n) 까지의 숫자 i 에 대하여 반복
  2-1. array[i] 가 false 인 경우, i 의 배수 index 에 대하여 array[index] 를 모두 true 처리
  2-2. 이전 i 의 배수는 모두 처리되었기 때문에 i 의 배수 작업은 i * i 부터 수행

3. 최종적으로 true 인 요소 => 합성수

const array = new Array(n + 1).fill(false);

for (let i = 2; i * i <= n; i++) {
  if (!array[i]) {
    for (let j = i * i; j <= n; j += i) {
      array[j] = true;
    }
  }
}

return array.filter(Boolean).length;

 

후기

'에라토스테네스의 체'
소수 & 합성수에 관한 문제를 풀 때 반드시 알아야 하는 중요한 공식이다. 반드시 기억하자.