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

문제

풀이

1. 소수 구하기

def is_prime_number(num):
    num = int(num)
        
    if num < 2:  
        return False

    for i in range(2, int(num**(1/2)) +1 ):
        if num % i == 0:
            return False 
    return True

 

0,1은 소수가 될 수 없으므로 조건 처리를 해주고,

2부터 num까지의 수로 num을 나누어 하나라도 몫이 0이되면(나누어 떨어지면) False를 리턴해주는 함수이다.

이때, 시간복잡도를 줄이기 위해 for문을 num까지 돌리는 것이 아닌 num의 제곱근까지만 돌리도록 해주었다.

 

2. K진수 구하기

def k_number(n,k):
    string = ''
    while n>0:
        string += str(n%k)
        n //= k       
    return string[::-1]

 

n이 0이 될때까지 k로 나누어 해당 수를 string에 붙여주었다.

이때 k진수는 string을 뒤집은 수가 된다.

혹은 string += str(n%k) 대신 string = str(n%k) + string 으로 식을 써주고 string을 리턴해주어도 된다.

 

3. 0을 기준으로 나누어 소수인지 판별

def solution(n, k):
    answer = 0
    k_num = k_number(n, k)
    nums = str(k_num).split('0')

    for num in nums:
        if num and is_prime_number(num):
            answer+=1
    return answer

 

코드

def is_prime_number(num):
    num = int(num)
        
    if num < 2:  
        return False

    for i in range(2, int(num**(1/2)) +1 ):
        if num % i == 0:
            return False 
    return True

def k_number(n,k):
    string = ''
    while n>0:
        string += str(n%k)
        n //= k       
    return string[::-1]

def solution(n, k):
    answer = 0
    k_num = k_number(n, k)
    nums = str(k_num).split('0')

    for num in nums:
        if num and is_prime_number(num):
            answer+=1
    return answer

 

프로그래머스