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

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

1. 문제

2. 생각의 흐름

1. 10진수 -> n진수로 변환한다
2. 변환된 n진수에서 소수인지 판별할 수를 뽑는다.
   2.1 예를들어 2110 이면 2,21,211 이런식으로 수를 만들려고 했다.
   2.2 문제를 풀다보니 2110 -> 211 만 뽑혀야 하는것을 파악
   2.3 변환된 n진수를 0으로 스플릿 하여 리스트에 저장
3. 새로 추출한 숫자 리스트의 소수가 몇개인지 소수판별하여 개수 리턴

3. 나의 풀이

import math
def primality(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 conversion(n,q):
    rev_base=''
    while n>0:
        n,mod=divmod(n,q)
        rev_base+=str(mod)
    return rev_base[::-1]

def solution(n, k):
    answer=0
    num=conversion(n,k)
    num_list=num.split('0')
    for l in num_list:
        if len(l)>0:
            if primality(int(l)):
                answer+=1
    return answer

4. 느낀점

소수 판별 알고리즘, n진수 변환은 많이 나오는듯 하니 외우자.