[Python] 프로그래머스 Lv2 - k진수에서 소수 개수 구하기 (2022 KAKAO BLIND RECRUITMENT)

🔗 문제링크

코딩테스트 연습 - k진수에서 소수 개수 구하기

📂 분류

구현

💡 풀이

단순 구현 문제였는데 에라토스테네스의 체를 이용해 소수를 구하려고 했으나 범위를 얼마나 지정해야 줘야 알 수 없기에 단순하게 소수를 구하는 로직을 구현했다. 

 

에라토스테네스의 체를 이용하면 1번과 11번이 런타임 오류가 발생한다.

 

접근 방식

• n을 k진수로 바꿔준다.
• 문제 설명에 나와있는 조건에 따라 소수는 '0'을 split 한 숫자이다.

💻 코드

def convert(num, base):
    if base == 10:
        return str(num)

    code = "0123456789"
    ret = ''

    while True:
        if num < base:
            ret += str(code[num])
            break
        num, mod = divmod(num, base)
        ret += code[mod]

    return ret[::-1]


def isPrimeNumber(n):
    if n == 1:
        return False

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


def solution(n, k):
    answer = 0

    split = convert(n, k).split('0')

    for num in split:
        if num == '':
            continue
        if isPrimeNumber(int(num)):
            answer += 1

    return answer