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

다음 2가지를 해야 하는 문제이다.

• 소수판정
• n을 k진수로 변환

수가 n까지 주어져서 에라토스테네세의 체로 n까지 소수여부를 모두 계산해두려 했는데, k진수로 바꾼 후 살피므로 n을 넘는 매우 긴 수도 등장한다. 따라서 $\sqrt{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