[프로그래머스] k진수에서 소수 개수 구하기 (python)

문제 요약

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

 

주어진 숫자 n을 k진수로 변환하고 아래 그림에 해당하는 10진수 P중에서 소수인 숫자의 개수를 세는 문제.

 

접근

일단 진수가 나와서 겁을 먹고 보자마자 도망쳤다...

하지만 알고 보니 별게 아니었던 것.

 

n이 0이 될 때까지 k로 나누면서 나온 나머지값을 통해 k진수로 변환해주고,

나온 값들에 대해 0을 기준으로 찢어서 배열에 넣어줬다.

 

배열에 있는 값에 대해 소수인지 판별해주었다. 

find_prime에서 p보다 작은 숫자들을 나누었을 때 나눠지는 값이 아니면 False를 반환한다.

이때 반복문의 횟수를 반으로 줄이기 위해  int(math.sqrt(p))까지만 돌린다.

 

코드

import math


def solution(n, k):
    def find_prime(p):
        for i in range(2, int(math.sqrt(p)) + 1):
            if p % i == 0:
                return False

        return True

    answer = 0

    # k진수로 변환
    num = ""
    while n > 0:
        num = str(n % k) + num
        n //= k

    arr = num.split("0")

    # 소수찾기
    for i in arr:
        if i == "" or i == "1":
            continue

        if find_prime(int(i)):
            answer += 1

    return answer

 

 

회고

문제 읽고 지레 겁먹지 말 것. 

소수 판별 문제 백년만에 풀어서 처음에 살짝 멈칫했다.