[Algorighm] k진수에서 소수 개수 구하기

문제설명

k진수에서 소수 개수 구하기는 정수 n을 k진수로 변환한 뒤 0을 기준으로 분리된 수에서 소수의 갯수를 찾아 반환하는 문제이다.

문제풀이

핵심은 소수찾기이다. 소수는 자기 자신과 1만을 나머지 수로 가지는 수.

소수 찾기 방법 중 가장 시간복잡도가 낮은 제곱근 판별을 사용한다.

function isPrime(num) {
  
  if(num <= 1) {
    return false;
  }
  // 2 이상부터 나눠떨어지면 소수가 아니다
  for(let i = 2; i <= ~~(Math.sqrt(num)); i++){
    if(num % i === 0){
      return false; 
    }
  }
  return true; 
}

이후로는 간단하다. k진수로 변환 후 0으로 끊은 배열 생성후 isPrime의 조건에 맞는 요소 배열의 길이를 반환한다.

function solution(n, k) {
    return n.toString(k).split('0').filter(e=>isPrime(+e)).length;
}