[프로그래머스] k진수에서 소수 개수 구하기 - 파이썬

https://programmers.co.kr/learn/courses/30/lessons/92335?language=python3 

코딩테스트 연습 - k진수에서 소수 개수 구하기

def make_num(n,k):
    num_str = ""
    while True:
        m = n % k
        n = n // k
        num_str += str(m)
        if n == 0:
            break
    return num_str[::-1]
def check(a):
    if a == 2:
        return True
    
    b = int(a**(1/2))
    for i in range(2,b+1):
        if a%i == 0:
            return False
    return True

def solution(n, k):
    answer = 0
    num = make_num(n,k)
    num_list =list(num.split("0"))
    num_list_n = []
    for i in range(len(num_list)):
        if num_list[i] == '1' or num_list[i] == '':
            pass
        else:
            num_list_n.append(num_list[i])
    for i in range(len(num_list_n)):
        if check(int(num_list_n[i])):
            answer +=1
            
    return answer

이문제는 그냥 할만했다. 우선 n진수로 만들어주고

그다음 소수 판별이다.

소수를 판단하는 방법은 아주 다양하지만 모든 수를 고려해서 푸는 법이 있다!

하지만 이것도 무지 긴수에서는 힘들다 그래서 나는 어케 테스트 케이스 1에서 계속 시간초과의 문제를 겪었다

이걸 해결하기 위해 찾아 보았는데 나는 그냥 절반까지만 고려해도 충분하다고 생각했지만 

어떤 사람이 글을 써놓은 것을 보니 n의 제곱근까지 고려해도 충분히 소수 판별이 가능하다는 글을 보고 

바로 적용해보니 해결

 

이문제는 그냥 할만했다

핵심은 n진수 변환, 스플릿, 소수판별 끝