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

프로그래머스 카카오 Lv2 문제풀이

• 나의 풀이

// 소수 판별 함수
const isPrime = (arg) => {
  if (arg < 2) return false;
  // Math.sqrt() 범위를 제곱근까지로 설정
  for (let i = 2; i <= Math.sqrt(arg); i++) {
    if(arg % i === 0) return false;
  }
  return true;
}

// 0을 기준으로 구분하고 소수 요소만 남기는 배열을 구하여 그 길이를 리턴
function solution(n, k) {
  return n.toString(k).split('0').map(Number).filter(el => isPrime(el)).length;
}

 

• 소수 구하는 식이 왜 제곱근 까지인가?

많은 포스팅에서 "제곱근을 기준으로 대칭으로 곱이 이루어지기 때문에" 라고 적혀 있었는데 무슨 말인지 이해가 안가서 혼자 고민하다가 깨달은 내용을 적어놓으려고 한다.

예를 들어 36 이라는 숫자를 보자면 36의 제곱근은 6이다( -> 6 * 6 = 36).

그렇다면 6이 아닌 어느 두개의 숫자를 곱하여 36을 만들기 위해서는 한쪽이 6보다 작고 반대쪽은 6보다 커야 한다.

식으로 표현하자면,

a x b = 36 일때

a 가 6보다 작다면, b 는 반드시 6보다 커야 한다.

(1x36, 2x18, 3x12, 4x9, 6x6)

 

즉, 어떤 수의 약수 중에서 최솟값(1 제외)은 그 수의 제곱근보다 작거나 같다.

고로, 어떤 수가 소수인지 판별하기 위해서는 1과 자신을 제외한 수 중에서 약수가 존재하는지만 파악하면 되기 때문에

확인하는 숫자 범위를 2 와 제곱근 사이로 설정하면 된다.