[알고리즘 JS] 프로그래머스 LV.1 소수 찾기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12921?language=javascript 

프로그래머스

풀이 1

function solution1(n) {
  // 입력 : 2 이상 자연수 n
  // 출력 : 1과 n 사이의 소수의 갯수

  let cnt = 0;

  for (let i = 1; i <= n; i++) {
    let flag = true;
    if (i === 1) flag = false;
    for (let j = 2; j <= Math.sqrt(i); j++) {
      if (i % j === 0) flag = false;
    }
    if (flag) cnt++;
  }
  return cnt;
}

console.log(solution1(10));

• 기존에 사용했던 소수를 찾는 방법을 활용했다. 
• 1부터 n까지의 각 수를 반복문으로 반복하며 소수인지 판별하는 방식
• 안쪽 for문에서 2부터 각 수의 제곱근까지 비교해서 나누어 떨어지지 않은 경우에는 카운트를 추가했다.
• 2중 for문에 비교해야 하는 수가 많아서 그런지 정답처리는 되었지만, 시간 초과 오류가 났다.

풀이 2

function solution2(n) {
  // 입력 : 2 이상 자연수 n
  // 출력 : 1과 n 사이의 소수의 갯수
  let cnt = 0;
  let arr = new Array().fill(0);

  // 2부터 시작하여 범위까지 반복하고, 그 값을 배열에 추가한다.
  // 소수는 2부터 시작하기 때문에, i도 2부터 시작한다.
  for (let i = 2; i <= n; i++) {
    arr[i] = i;
  }

  // 2부터 범위까지 반복하면서 배열을 순회한다.
  for (let i = 2; i <= n; i++) {
    // 현재 탐색중인 배열이 이미 0 (지워진 값) 이면 건너뛴다.
    if (arr[i] === 0) continue;

    // 만약 존재하는 값이라면, 해당 수의 배수부터 출발하여 n의 범위까지,
    // 현재 수(i)의 배수만 방문하여 초기화한다.
    for (let j = 2 * i; j <= n; j += i) {
      arr[j] = 0;
    }
  }

  // 다시 배열로 돌아와서, 해당 배열의 값이 0이 아니면 소수이므로 카운트를 증감한다.
  for (let num of arr) {
    if (num) cnt++;
  }
  return cnt;
}

console.log(solution2(10));

• 시간초과 오류 때문에 방법을 찾다가 에라토스테네스의 체 방식으로 풀었다.
• 에라토스테네스의 체는 소수를 대량으로 빠르고 정확하게 구하는 방법으로, 주로 특정 범위가 주어졌을 때 그 범위 안에 소수의 개수를 구할 때 사용한다.
• 소수를 판별할 범위 만큼 배열을 만들고 값을 할당한 뒤, 조건에 맞게 하나씩 지우는 방법이다.
• 에라토스테네스의 체가 소수인 자기 자신을 제외하면, 해당 소수의 배수는 모두 합성수가 아닌 원리를 활용해 배열에서 그 배수를 모두 지우는 방식으로 소수를 구하는 것이다. 

느낀 점

알고리즘 문제를 풀면서 소수 관련 문제가 나오면 주로 내가 편하게 사용했던 방식을 고집하곤 했는데, 에라토스테네스의 체 알고리즘이 생각보다 크게 어렵지 않은 것 같았다. 앞으로 더 익숙해지고 이해가 잘 될 수 있게 많이 활용해봐야겠다.