[프로그래머스] 'k진수에서 소수 개수 구하기 ' 문제 자바스크립트 알고리즘

---

https://school.programmers.co.kr/learn/courses/30/lessons/92335

Q. k진수에서 소수 개수 구하기

---

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

---

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

입출력 예

---

n	k	result
437674	3	3
110011	10	2

• 코드

function solution(n, k) {
  let cnt = 0;
  const s = n.toString(k).split("0");
  s.forEach((num) => {
    if (isPrime(+num)) cnt++;
  });

  return cnt;
}

function isPrime(num) {
  if (num <= 1) {
    return false;
  }

  if (num % 2 === 0) {
    return num === 2 ? true : false;
  }

  const sqrt = parseInt(Math.sqrt(num));

  for (let divider = 3; divider <= sqrt; divider += 2) {
    if (num % divider === 0) {
      return false;
    }
  }

  return true;
}

Tip

소수 구하는 공식을 제곱근을 활용한 공식을 써야함
그렇지 않으면 시간 초과

에라토스테네스의 체

1을 제외하고 2부터 N까지 자신을 제외하고 순차적으로 자신의 배수들을 지워가면 결국에는 소수들만 남는다는 원리이다. n까지가 아니라 √n까지만 검사해도 결과는 같다.

예를 들어 N = 25 이라고 가정해보자.

1은 소수가 아니기 때문에 2부터 실행한다.
2를 제외하고 2의 배수를 모두 제거한다. [4,6,8,10,12,14,16,18,20...제거]
3을 제외하고 3의 배수를 모두 제거한다. [9,15,21,24...제거] _6,18... 등은 2의 배수에서 이미 제거됨
4는 이미 삭제되었다.
5를 제외하고 5의 배수를 모두 제거한다[25,35,45,55... 제거]____(5의 제곱이 나오기 전까지 모든 5의 배수는 이미 삭제되었다)
6은 이미 삭제되었다.
따라서 √25(5)까지만 검사하면 된다. √25(5)이후의 배수들은 이미 삭제되었기 때문이다.
(여기서 n은 25라 가정 , 1부터 25까지의 5의 배수는 25를 제외하고 이미 지워진 상태이다 )

참고