k진수에서 소수 개수 구하기 (Level 2)

문제

 

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

프로그래머스

 

내 풀이

 

n을 k진수로 변환한 다음 '0'을 기준으로 잘라주었다. '0'을 자른 후에 사이사이 ''이 섞여있으므로 ''을 제거해주었다.

 

소수인지 판별하는 함수를 구하였다. 입력 숫자의 (제곱근+1)만큼 for문을 돌려서 계산하면 된다. 

 

소수인지 판별하는 함수로 정답을 구하면 된다.

 

import math

def solution(n, k):
    answer = 0
    num = ''
    while n:
        num += str(n % k)
        n //= k
    num = num[::-1].split('0')
    num = [int(x) for x in num if x != '']
    
    def is_prime(n):
        if n == 1: return False
        for i in range(2, int(math.sqrt(n))+1):
            if n % i == 0: return False
        return True
    
    for a in num:
        if is_prime(a): answer += 1
    
    return answer

 

총평

처음에 에라토스테네스의 체로 풀었다가 런타임 에러가 났었다. 찾아보니 지나치게 큰 수에 에라토스테네스의 체를 적용하면 효율성이 떨어지기 때문에 적합하지 않다고 하였다. 

그래서 각 숫자마다 소수인지 판별하는 코드로 다시 구현하였다.