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

 

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

n을 k진수로 변환하고(n이 0이 될 때까지 k로 나눈다.),

0을 포함하지 않는 수만 분리하여(split('0'))

소수인지 판별해주면 된다. 

 

처음엔 findPrime에서 반복문의 범위를 (2, num//2)로 설정해줬었는데, tc1에서 시간 초과가 났다. 

그래서 범위를 다시 (2, 제곱근+1)로 설정해줬다.

 

# 프로그래머스 92335: k진수에서 소수 개수 구하기 (2022 KAKAO BLIND RECRUITMENT)

def findPrime(num): # 소수 찾기
    if num == 1:
        return False
    for i in range(2, int(num**(1/2))+1):
        if num % i == 0:
            return False
    return True

def solution(n, k):
    s = ''
    while n > 0: # k진수로 변환
        s = str(n % k) + s
        n //= k
    
    answer = 0
    for i in s.split('0'):
        if i != '':
            if (findPrime(int(i))):
                answer += 1
            
    return answer