function solution(n, k) {
const isPrime = (num) => {
if (num === 1) return false;
if (num === 2) return true;
for (let i = 2; i*i <= num; i++) {
if (num % i === 0) return false;
}
return true;
};
return n
.toString(k) // k진수로 변경한 후
.split("0") // 0을 기준으로 소수인지를 판별할 수 있기 때문에 0으로 split
.filter((el) => el.length !== 0) // 000 처럼 연속적인 경우 빈 배열이 나오기때문에 제거
.filter((el) => sosu(Number(el))).length; // 남은 판별을 위한 수들을 함수를 이용해 정리
}
* 특정 수가 소수인지를 구하는 문제는 위의 isPrime 방식으로 구하면 제일 빠르게 구할 수 있고
특정 수 까지 소수인지를 구하는 방법은 에라토스테네스의 체를 이용하면 된다.
-> 에라토스테네스의 체란?
2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 오른쪽에 2를 쓴다. 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
