[프로그래머스/파이썬] k진수에서 소수 개수 구하기

내 풀이

from math import sqrt


def solution(n, k):
    answer = 0
    
    # n을 k진수로 변환
    def n_to_k(n, k):
        # 진수값의 최대 설정
        upper_limit = 0
        while k**(upper_limit+1) < n:
            upper_limit += 1
		
        # 앞쪽 진수값부터 차례로 처리
        k_num = ""
        while upper_limit >= 0:
            k_num += str(n // k**upper_limit)
            n -= (k**upper_limit) * (n // k**upper_limit)
            upper_limit -= 1
        return k_num
    
    # 소수 확인
    def check_prime(num):
        # 1은 제외
        if num == 1:
            return False
        
        # 쌍을 이루기 때문에 전체를 볼 필요 없이 제곱근까지만 확인
        for denominator in range(2,int(sqrt(num))+1):
            if num % denominator == 0 :
                return False
        return True
    
    
    k_num = n_to_k(n, k)
    for num in k_num.split("0"):
        if num: # 0이 여러개인 경우 방지
            answer += check_prime(int(num))
    
    return answer

 

메모

특정 범위 내의 소수를 찾는 빠른 알고리즘 : 에라토스테네스의 체 https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4