[프로그래머스] 2022 KAKAO BLIND RECRUITMENT - k진수에서 소수 개수 구하기

문제

프로그래머스

첫 번째 풀이(틀림, 88.1, TC1번 시간초과)

def translation(n, k):
    rev_base = ''
    while n > 0:
        n, mod = divmod(n, k)
        rev_base += str(mod)

    return rev_base[::-1] 

def check(x):
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    if x==1:
        return 0
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return 0 # 소수가 아님
    return 1 # 소수임

def solution(n, k):
    answer = 0
    number=translation(n,k) # 문자열
    target=''
    
    for i in range(0,len(number)):
        if number[i] !='0':
            target+=number[i]
            if i==(len(number)-1):
                answer+=check(int(target))
                target=''
        
        elif number[i]=='0':
            if target!='':
                answer+=check(int(target))
                target=''
            else:
                pass
    
    return answer

 

소수인지 판단하는 부분을 2부터 x-1까지 모두 나누면서 하다보니까 시간이 오래걸림, 최대 999998번수행

제곱근 비교를  통해서 시간을 단축 시킨다.

2부터 제곱근까지 비교

어떤 수가 소수인지 여부를 확인할 때, 그 수의 제곱근까지만 확인하면 충분함, 제곱근을 넘어가는 약수는 이미 제곱근 이하의 약수와 짝을 이루기 때문에 검사할 필요가 없다. 약 1000번 수행

 

두 번째 풀이(정답)

import math
def translation(n, k):
    rev_base = ''
    while n > 0:
        n, mod = divmod(n, k)
        rev_base += str(mod)

    return rev_base[::-1] 

def check(x):
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    if x==1:
        return 0
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return 0 # 소수가 아님
    return 1 # 소수임

def solution(n, k):
    answer = 0
    number=translation(n,k) # 문자열
    target=''
    
    for i in range(0,len(number)):
        if number[i] !='0':
            target+=number[i]
            if i==(len(number)-1):
                answer+=check(int(target))
                target=''
        
        elif number[i]=='0':
            if target!='':
                answer+=check(int(target))
                target=''
            else:
                pass
    
    return answer