[파이썬(python)] 2022 카카오 블라인드 공채 k진수에서 소수 개수 구하기

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

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

이 문제는 옛날에 소수 판별 알고리즘을 구현했던 것이 기억나서 쉽게 풀었다.

 

import math
def change(n, k):
    #k 진수로 변환. 결과는 string
    string = ''
    q, r = divmod(n, k)
    if q == 0 :
        return string + str(r) 
    else :
        return change(q, k) + str(r)

def isprime(n):
    #n이 소수인지 판별하는 알고리즘
    if n == 1:
        return False
    
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
        
    return True
    
def solution(n, k):
    answer = 0
    change_k = change(n, k)
    
    p = change_k.split('0')
    
    p = [int(v) for v in p if v]
    #공백제거
    
    for i in p:
        if isprime(i):
            #소수이면
            answer += 1
    
    
    return answer