📌 [Programmers] k진수에서 소수 개수 구하기

📖 문제

📖 예제

📖 풀이

def solution(n, k):
    answer = 0
    num = ''
    # k진수로 변환하는 방법
    while n > 0:
        num = str(n % k) + num
        n = n // k
    num = num.split('0')
    
    for i in num:
        if i != '':
            if int(i) < 2:
                continue
            else:
                check = True
                # 소수 확인
                for j in range(2, int(int(i)**0.5)+1):
                    if int(i) % j == 0:
                        check = False
                        break
                if check:
                    answer += 1
    return answer

해당 문제를 통해 k진수로 변환하는 방법과 소수를 확인하는 가장 효율적인 방법인 '에라토스테네스의 체'를 배울 수 있었다.
1. 특정 수를 k진수로 변환하기 위해서 특정 수에서 k를 나눈 나머지를 기존 수의 앞으로 붙여주는 수행을 특정 수가 0이 될 때까지 반복해준다.
2. 어떤 수가 소수가 아니라면, 그 수의 최소 소인수는 그 수의 제곱근 이하에 존재한다는 사실을 바탕으로 제곱근까지만 확인하여 나누어 떨어지는 수가 있는지를 확인한다.