다음 2가지를 해야 하는 문제이다.
수가 n까지 주어져서 에라토스테네세의 체로 n까지 소수여부를 모두 계산해두려 했는데, k진수로 바꾼 후 살피므로 n을 넘는 매우 긴 수도 등장한다. 따라서 까지 계산하는 방법을 이용해야 한다.
추가로 k진수 변환하는데 삽질을 했는데 다음엔 빠르게 하자
# n이 소수인지 판정(에라토스테네스의 체는 너무 오래걸림, 루트n까지 탐색하는 방법써야함)
def isprime(n):
if n <= 1:
return False
i = 2
while i*i <= n:
if n%i == 0:
return False
i += 1
return True
# n을 k진법으로 변환
def convert_n_to_k_base(n,k):
converted_n = ''
while n > 0:
n, mod = divmod(n, k) # 몫, 나머지 반환
converted_n = str(mod) + converted_n
return converted_n
def solution(n, k):
answer = 0
# k진법으로 변환한 문자열 구하기
converted_n = convert_n_to_k_base(n,k)
# 0으로 split하기
splited_nums = converted_n.split("0")
# split된 각각이 소수인지 체크
for num in splited_nums:
if num != '' and isprime(int(num)):
answer += 1
return answer