[프로그래머스 코딩테스트 연습문제] 소수 찾기 | 알고리즘 설명 & 문제 풀이 with 자바스크립트(Javascript)

1. 문제 설명(요약)

2. 첫번째 문제 풀이(2024-01-02) faild

이번 문제는 숫자 n의 범위에 대해서 소수가 몇개인지를 찾는 알고리즘을 구현하는 문제입니다. for문을 2부터 n까지 (실질적으로 0과 1은 소수로 치지 않기 때문에) 돌리는데

두번째 for문에서는 2부터 n의 제곱근까지의 범위로 설정하고 (수학 공식 중 하나로, 소수를 구하는 범위는 해당 숫자를 2부터 숫자의 제곱근 까지의 숫자들로 나눌 때 0으로 떨어지지 않을 때 소수라고 합니다.) 각 i의 값(2부터 n까지의 값들)들이 소수인지를 판별한 후 소수일 경우 result를 누적시켜 반환하는 방법입니다.

이 방법의 경우 에라토스테네스의 체? 라는 수학 공식에서 나온 공식이라는데 음... 그냥 저는 보기를 포기하겠습니 ㄷ...

어찌 되었든 테스트케이스는 다 통과했는데 효율성 테스트에서 3개를 통과하지 못했더라고요. 음... 일단 한 번 나중에 더 찾아봐야 겠습니다.

function solution(n) {
  let result = 0;

  for (let i = 2; i <= n; i++) {
    let check = true; // 

    for (let j = 2; j <= Math.sqrt(i); j++) { // 해당 숫자(i) 가 소수인걸 알기 위해서는 2부터 해당 수의 제곱근까지의 범위로 돌리면서 됩니다.
      if (i % j === 0) {
        check = false;
        break;
      }
    }
    result += check ? 1 : 0 // check가 true, 즉 true(소수) 인 상태면 result에 1을 누적 증가, 아닐 경우 0을 누적 할당
  }
  return result;
}