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

문제

# deque 사용을 위해(O(1))
import collections

# k진수로 변환하는 함수
def knumber(n, k):
    answer = ''
    while n >= k:
        a = n // k
        b = n % k
        answer = str(b) + answer
        n = a
    answer = str(a) + answer
    return answer
   
# 소수인지 확인하는 함수
def decimal(n):
    # 1은 제외
    if n == 1:
        return False
    # 2는 포함
    if n == 2:
        return True
    # 짝수 제외
    if n % 2 == 0:
        return False
    # 3부터 시작해서 2씩 올리기
    r = 3
    while r < int(n**0.5)+1:
        if n % r == 0:
            return False
        r += 2
    return True

def solution(n, k):
    answer = 0
    # k진수로 변환
    Three = knumber(n, k)
    # 0을 기준으로 슬라이싱
    Three = Three.split('0')
    Three = collections.deque(Three)
    # 소수 판별하여 count
    while Three:
        i = Three.pop()
        # '' 빈열이 있으면 continue
        if i == '' or i == '0':
            continue
        if decimal(int(i)):
            answer += 1
    return answer