k진수에서 소수 개수 구하기

📖 2022 KAKAO BLIND RECRUITMENT > k진수에서 소수 개수 구하기

📖What I thought

• 그냥 진법 변환 후 소수 구하기! 하면 끝 아니야? 했는데 정말 끝이였음
• 소수 구할 때 제곱근까지만 나눠보면 된다는 것이 포인트 시간단축에 큰 효과가 되었움^ㅡ^

📖풀이

📎구현

def is_prime(c):
    if c < 2:   # 0, 1은 소수가 아님
        return False
    if c % 2 == 0:   # 짝수는 2만 소수
        return c == 2
    
    i = 3
    while i * i <= c:
        if c % i == 0:
            return False
        i += 2   # 홀수만 검사
    return True    
 
def solution(n, k):
    tmp = ""
    while n > 0:
        tmp += str(n%k)
        n //= k
    
    cand = list(filter(lambda x: len(x)>0 , tmp[::-1].split('0')))
    
    prime = 0
    for c in cand:
        prime += is_prime(int(c))
    
    return prime

📖What I learned

• string += 연산보다 list로 만들어 append하고 나중에 ''.join() 연산이 더 빠르다는 것을 알아두자
• 소수 구할 때 시간 줄이기!! → n까지 나눠보는 것이 아니라 n의 제곱근까지만 나눠보면 됨!!

📖관련 지식

📎filter