TIL - 20221013

주의! 본 게시물은 k진수에서 소수 개수 구하기 문제에 대한 중요 내용을 포함하고 있습니다. 풀기 전이시라면 이 점 참고해주시길 바랍니다!

 

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

프로그래머스

 문제를 읽으면서 바로 든 생각은 주어진 수 n을 주어진 k진수로 변환하는 것과, 소수 판별법이었다. 먼저 소수 판별법은 다음과 같은 방법들이 존재한다는 사실을 오늘 알게 됐다.

• 반복문을 이용해 나누어지는 수가 존재하는지 계산하는 방법
• 주어진 수 / 2까지만 나누어서 계산하는 방법
• 주어진 수의 제곱근까지만 나누어서 계산하는 방법

 첫 번째 방법은 2부터 시작해서 주어진 수 - 1까지 나눠보고 나눠지는 수가 존재한다면, 소수가 아니라는 뜻이므로 가장 쉽고 간단하게 소수를 판별할 수 있는 방법이다.

 두 번째 방법도 첫 번째 방법과 과정을 동일하지만, 첫 번째 방법의 딱 절반만큼 실행하면 되므로 시간을 절약할 수 있다.

 세 번째 방법이 두 번째 방법보다도, 가장 빠른 방법이다. 소수를 판별하는 데에 있어서 제곱근보다 큰 수까지 돌릴 필요가 없다고 한다. 그러므로, Math.sqrt()를 통해 주어진 수의 제곱근을 구하고 제곱근까지만 반복문으로 나눠보며 나눠지지 않는다면, 소수인 것이다.

 

 자바스크립트에서 주어진 수 n을 k진수로 변환하는 방법은 n.toString(k)로 쉽고 간단하게 변환할 수 있다.