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

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

프로그래머스

 

 

위 문제는 시간 초과를 피하는게 키포인트인 문제이다. 

 

알아야할 것

1. 10진수 k진수로 바꾸는 법

- n인 10진수가 있으면 이거를 k로 계속 나눴을 때, 나머지들을 나열한거임. 

자세한건 아래 링크 참조 부탁함.

https://m.blog.naver.com/icbanq/221727893563

[진법변환] 2진수,8진수,10진수,16진수 쉽게 변환하는 방법 알아보기!

 

 

2. 소수 판별 법 (최적화 된 방법)

- 원래 n이 소수인지 아닌지 판별하는 법은 2부터 n-1까지 나눠보는 거임

- 하지만, n-1까지 나눠볼 필요없이 조금 적게하는 방법은 n의 제곱근까지만 나눠보면 됨. 

- 파이썬에서 제곱근은 math.isqrt() 함수가 존재함. (import math필수)

import math
div_range = math.isqrt(int_i) +1

 

 

 

 

첫 시도 (1번 테스트만 시간 초과)

def solution(n, k):    
    store_binary = ""
    answer = 0
    
    while True:
        a = n%k
        store_binary = str(a) + store_binary
        
        n //= k
        
        if n < 1:
            break
    
    primer_check = list(store_binary.split('0'))
    
    for i in primer_check:
        if i == '':
            pass
        elif i == '1':
            pass
        else:
            Is_primer = 0
            int_i = int(i)
            for j in range(2, int_i//2):
                if int_i%j == 0:
                    Is_primer = 1
                    break
                    
            if Is_primer == 0:
                answer += 1
    return answer

 

정답 : isqrt() 함수 적용

# 진수 바꾸는 방법 알기
# 소수 판별 법 (최적화된 방법)

import math

def solution(n, k):    
    store_binary = ""
    answer = 0
    
    while True:
        a = n%k
        store_binary = str(a) + store_binary
        
        n //= k
        
        if n < 1:
            break
    
    primer_check = list(store_binary.split('0'))
    
    for i in primer_check:
        if i == '':
            pass
        elif i == '1':
            pass
        else:
            Is_primer = 0
            int_i = int(i)
            div_range = math.isqrt(int_i) +1
            for j in range(2, div_range):
                
                if int_i%j == 0:
                    Is_primer = 1
                    break
                    
            if Is_primer == 0:
                answer += 1
    return answer

 

테스트 1 〉

통과 (135.03ms, 10.2MB)

 

근데 이래도 테스트 1은 135.03ms 나옴;;;