[프로그래머스] 소수 찾기

소수는 1과 자기자신 외의 약수를 갖지 않는 수이다.

소수를 판별하기 위해 2부터 자기자신-1 까지 나누어지는지 확인해야 한다.

아래 두가지 방법을 통해 효율성을 높일 수 있다!

 

1. 약수는 짝을 가진다는 특징을 활용

10 = (1, 10), (2, 5), (5, 2), (10,1)

16 = (1,16), (2, 8), (4, 4), (8, 2), (16, 1)

이 짝은 자신의 양의 제곱근을 기준으로 지어진다. (10 -> 3.162.. 16 -> 4 )

따라서, 2부터 자신의 양의 제곱근 까지 나누어지는지 확인하면 된다!

 

2. 모든 짝수는 소수가 아니다라는 특징을 활용

모든 짝수는 2로 나누어지기 때문이다.

따라서, 짝수의 소수 여부를 확인하지 않아도 되고(소수가 아니기 때문)

나머지 값들을 2의 배수들로 나누어보지 않아도 된다.(2의 배수로 나누어지는 값은 2로도 나누어지기 때문에 이미 걸려졌음)

 

자세한 내용은 아래 주석을 확인 !

 

function solution(n) {
  // 전체 개수에서 소수가 아닌 값들을 제거해 나갈 것
  // 짝수(2의 배수)의 개수를 제거함
  var answer = n - parseInt(n / 2);

  // i = 나누어지는 값 역할
  // 3~n 까지 소수 가능여부 판별
  // i가 2씩 커짐: 짝수에 해당하는 수는 제거했기 때문 (3,5,7,9..)
  for (let i = 3; i <= n; i += 2) {
  
    // k = 나누는 약수 역할
    // 3~자신의 제곱근 까지의 수로 나누어지는지 확인:
    // answer를 선언 할 때 2의 배수에 해당하는 값들은 제거했기 때문
    // k또한 2씩 커짐: 2로 나누어지는 값들을 이미 제거했기 때문
    // 4로 나누어지는 값은 2로도 나누어져서 이미 제거되었기 때문!
    for (let k = 3; k <= Math.sqrt(i); k += 2) {
      if (i % k === 0) {
        answer -= 1;
        break;
      }
    }
  }
  return answer;
}