프로그래머스 | #Lv1 "소수 찾기"

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

나의 풀이

function solution(n) {
  let answer = 0;
  const arr = new Array(n + 1).fill(true);
  const end = Math.sqrt(n);

  for (let i = 2; i <= end; ++i) {
    if (arr[i] === false) {
      continue;
    }
    for (let k = i * i; k <= n; k += i) {
      arr[k] = false;
    }
  }
  for (let i = 2; i <= n; ++i) {
    if (arr[i] === true) {
      answer++;
    }
  }
  return answer;
}

마무리

알고리즘을 공부하면서 소수를 구하는 방법을 익히지 못해서 검색이 필요했다.

체로 걸러주듯 숫자의 배수들을 지워주는 에라토스테네스의 체 라는 방법이 있다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

방법은 아래와 같다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

출처 : 위키백과

알고리즘은 풀면 풀수록 노하우가 생기는 것 같다. 

반응형