프로그래머스 / 소수찾기 ( + 에라토스테네스의 체 )

🌏 문제

• 문제 링크 : 프로그래머스 1단계 소수찾기

• 설명 : 1부터 입력받은 숫자까지의 소수의 개수를 리턴

• 입출력 예시
  10 => 4
  5 => 3

• 소수 : 1과 자기자신으로만 나눠지는 수 (1은 소수가 아님)

🌏 시도방법 1 (부족)

소수인지 아닌지를 판별하는 로직을 만든 경험이 있어서,
그때 사용한 로직으로 진행했다.

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

대부분의 테스트는 통과해도 효율성에 관한 테스트가 통과하지 않았다.

🌏 시도방법 2 (부족)

예전 다른 소수관련 문제를 풀 때,
다른 사람들은 Math.sqrt()를 사용해서 푼 걸 본 기억이 났다.
그래서 해당 메소드를 사용해 도전했다.

Math.sqrt() 는 제곱근을 반환한다.

제곱근을 이용해 소수를 판별하는 알고리즘에 대한 설명은
소수 여부 판단하는 알고리즘 에 잘 나와있다.
해당값의 제곱근 기준으로 곱셈이 대칭을 이루고 있어서
n의 제곱근까지 떨어지는 숫자가 있으면 소수가 아니라고 판단하는 방법이다.

function checkPrime(n) {
  for(let i = 2; i <= Math.sqrt(n); i ++) {
    if(n % i === 0) {
      return false;
    }
  }
  return true;    
}
function solution(n) {
  let answer = 0;
  for (let i = 2; i <= n; i ++) {
    if (checkPrime(i)) {
      answer = answer + 1;
    }
  }
  return answer;
}

처음 시도한 코드에서 함수가 2개의 역할을 하고 있어서,
이번에는 소수인지 판별하는 함수 (checkPrime) 를 따로 두었다.

이 코드도 효율성테스트를 통과하지 못했지만, 점수가 좀 올랐다.

🌏 시도방법 3 (통과)

내가 아는 방법을 모두 시도했고 더 이상 떠오르지 않았다.
질문하기 게시판을 통해 힌트를 찾아봤고, 에라토스테네스의 체를 활용하라는 답변을 보았다.

에라토스테네스의 체는 처음 들어보는 거라, 개념에 대해 살펴보았다.
위키백과/에라토스테네스의 체
(참고로 에라토스테네스는 지구의 크기를 처음으로 계산했다고한다..! 👏🏻)

1. n 까지의 수를 나열한다.
2. 2는 소수니까 소수목록에 정리하고, 2의 배수를 모두 지운다.
3. 3은 소수니까 소수목록에 정리하고, 3의 배수를 모두 지운다.
4. 4는 이미 2번 단계에서 지워져있다.
5. 5는 소수니까 소수목록에 정리하고, 5의 배수를 모두 지운다.
6. 이렇게 n까지 진행하면 소수를 찾아낼 수 있다.

사실 여기서도 나는 시행착오를 한 번 겪었다.
'2는 소수니까, 3은 소수니까, 5는 소수니까' 저 부분을
소수인지 아닌지 판별하는 함수에 입력으로 넣는 방식을 진행하였다.
그러나 테스트가 통과하지 않았고, 위키백과에서 다른 언어로 구현한 코드를 살펴봤다.
어떤 언어도 소수판별하는 코드가 따로 없었다.

그 부분을 고민해보니, 숫자로 남아있는 부분은 소수라는 걸 깨달았다.
소수가 아닌 숫자는 x의 배수를 지우는 작업을 할 때 지워진다는 것을 깨달았다.
우리가 맨 처음 2를 만난 건, 2가 소수이기 때문에 만난 것이다.
그래서 2x2인 4부터 +2 작업을 통해 쭉 지워나간다.
그 다음 만난 3도 소수이기 때문에 지워지지 않고 살아있는 것이다.
3x3인 9부터 +3 작업을 통해 쭉 지워나간다.
4가 없는 이유는 2의 배수에서 이미 4는 소수가 아니었기 때문이다.
이렇게 숫자를 하나하나 확인하며 소수판별기에 넣을 필요가 없다는 걸 깨달았다.
에라토스테네스의 체 알고리즘이 매우 쉽고 효율적이라는 생각이 들었다.

그렇게 완성 된 나의 코드다.

function solution(n) {
  let nums = [0, 1]; // index와 자연수를 맞추기위해 임의로 설정했다.
  let primeNum = 0
  // 배열 만들기
  for (let i = 2; i <= n; i ++) {
    nums[i] = true;
  }
  for (let i = 2; i <=n; i ++) {
    if (nums[i]){
      primeNum ++;
      for (let j = i * i; j <= n; j += i) {
        nums[j] = false;
      }
    }
  }
  return primeNum
}

심신안정이 오는 파란물결 🐳

🌏 후기

새로운 알고리즘을 배울 수 있어서 좋았다.
직접 코드로 구현하면서 제대로 이해하지 못해 옆길로 샜지만,
그 경험을 기반으로 에라토스테네스의 체를 더 이해할 수 있었다.
느려도 꾸준히 앞으로 나아가는 사람이 되고싶다.