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

문제 링크

코드

def convert(n, k):
    result = ""
    while n > 0:
        result = str(n % k) + result
        n //= k
    return result


def is_prime(n):
    if n < 2:
        return False
    
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
        
    return True


def solution(n, k):
    numbers = list(map(int, filter(None, convert(n, k).split('0'))))
    return list(map(lambda x: is_prime(x), numbers)).count(True)

리뷰

처음에는 에라토스테네스의 채를 이용하는게 중복된 계산도 줄일 수 있고 효율적이라고 생각했다. 하지만 입력값 제한이 1000000이기 때문에 메모리 오버플로우가 발생했다. 입력값이 크기 때문에 오버플로우가 발생할 수 있다는 사실을 생각했다면 런타임 에러 시 바로 의심할 수 있었을 것 같다.