🥞 오늘 한 일

• 알고리즘 코드카타
  • 소수 찾기

알고리즘 코드카타

소수 찾기

문제

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

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

풀이

꽤 간단할 거라고 생각했고 실제로 간단하게 풀었지만 효율성 테스트에서 계속 실패를 하여 결국 에라토스테네스의 체라는 개념까지 알게 된 문제였다.
다음과 같은 과정을 거쳤다.

STEP 1

function solution(n) {
  let result = 0;
  outer: for (let i = 2; i <= n; i++) {
    for (let j = 2; j <= parseInt(Math.sqrt(i)); j++) {
      if (i % j === 0) {
        continue outer;
      }
    }
    result++;
  }
  return result;
}

간단하게 풀었다. 정확성 테스트에서는 전부 통과했으나 효율성 테스트에서 전부 실패했다.

STEP 2

때문에 코드를 좀 변경하여, 2의 배수일때나 3의 배수일때는 continue하여 조금이라도 효율적으로 작동하도록 변경을 해보았다.

function isPrime(i) {
  for (let j = 2; j <= Math.sqrt(i); j++) {
    if (i % j === 0) {
      return false;
    }
  }
  return true;
}

function solution(n) {
  let result = 0;

  for (let i = 2; i <= n; i++) {
    if ((i % 2 === 0 && i !== 2) || (i % 3 === 0 && i !== 3)) {
      continue;
    }
    if (isPrime(i)) {
      result++;
    }
  }
  return result;
}

이 방법을 사용해도 효율성 테스트는 하나만 통과하고 나머지는 전부 실패했다.

STEP 3

그렇게 지속적인 실패로 인해 구글링을 해보던 도중 에라토스테네스의 체라는 개념을 알게 되었다.
해당 개념을 적용하여 문제를 풀어보았다.

function solution(n) {
  let arr = Array(n + 1).fill(true);
  arr[0] = false;
  arr[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (arr[i]) {
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false;
      }
    }
  }
  return arr.filter((el) => el).length;
}

간단히 말하면 n까지의 숫자만큼의 배열을 만들고 요소는 전부 true로 설정한 후, 반복문을 돌리며 i의 배수일 경우 소수가 아니므로 false로 만든 다음 해당 배열의 true인 값들만 길이를 가져와서 return 하는 방법이다.
사실 마음에 드는 문제는 아니었다. 내가 처음에 짠 코드도 맞는 방법이고, 이런 깊은 수학적 지식까지 요구하는 문제라면 이 개념을 모르고 풀기는 좀 어렵기 때문이다. 이 개념을 모르는 사람도 금방 풀 수 있는 문제라면 할 말은 없지만~