[프로그래머스] Lv2. k진수에서 소수 개수 구하기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

✍🏻코드

def trans(n, k):  # n을 k진수로 반환
        ret = ""
        while n > 0:
            ret += str(n % k)
            n = n //  k
        return ''.join(reversed(ret))
def isprime(x): # 소수 찾기
    if x == 2 or x == 3:
        return True
    if x % 2 == 0 or x < 2:
        return False
    for i in range(3,int(x**0.5)+1,2):
        if x%i == 0:
            return False
    return True

def solution(n, k):
    cnt = 0
    a = trans(n,k)
    arr = a.split('0')
    for i in arr:
        if i == '':
            continue
        if isprime(int(i)):
            cnt += 1
    return cnt

💡풀이

• n을 k진수로 변환한 값을 a라고 하면, a를 '0'으로 split해서 소수인지 판별하면 된다.
• 주의할 점은 소수를 찾을때 x까지 전부 탐색하게 되면 시간초과가 발생한다.
• 3부터 시작해서 짝수일때는 건너뛰고, x의 절반만큼 탐색해야 시간초과가 발생하지 않는다.