k진수에서 소수 개수 구하기(2022 KAKAO BLIND RECRUITMENT) - 파이썬

import math

def change(n, k):
    rev_base = ''

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

    return rev_base[::-1] 
    # 역순인 진수를 뒤집어 줘야 원래 변환 하고자하는 base가 출력
    
def prime(M):
    M = str(M)

    while(M.find("00") != -1):
        M = M.replace("00","0")

    tmp = M.split("0")
    cnt = 0

    for val in tmp:

        if(val == "1" or len(val) == 0):
            continue

        val = int(val)
        is_prime = 0

        R = int(math.sqrt(val))
        for j in range(2, R+1):
            if(val % j == 0):
                is_prime = 1
                break

        if(is_prime == 0):
            cnt +=1 
    
    return cnt

def solution(n, k):
    answer = -1
    if(k==10):
        answer = prime(n)
    else:
        answer = prime(change(n, k))
    
    return answer

문제요약

10진법을 n진법으로 나누고 0을 기준으로 쪼갰을 때 소수의 개수를 구하라.

설명

문제 대로 따라가보자.

def change(n, k):
    rev_base = ''

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

    return rev_base[::-1] 
    # 역순인 진수를 뒤집어 줘야 원래 변환 하고자하는 base가 출력

10진법을 n진법으로 바꾼다.

n진법으로 바꾸는 방법은 10진법을 계속 n으로 나눴을 때의 나머지를 구해주면 된다.

 

divmod는 몫과 나머지를 구해준다.

 

구한 값을 역순으로 뒤집어 주면 n진법으로 수를 바꿀 수 있다.

 

def prime(M):
    M = str(M)

    while(M.find("00") != -1):
        M = M.replace("00","0")

    tmp = M.split("0")
    cnt = 0

    for val in tmp:

        if(val == "1" or len(val) == 0):
            continue

        val = int(val)
        is_prime = 0

        R = int(math.sqrt(val))
        for j in range(2, R+1):
            if(val % j == 0):
                is_prime = 1
                break

        if(is_prime == 0):
            cnt +=1 
    
    return cnt

소수를 구해주는 메소드이다.

 

00인 경우는 0으로 바꿔주었다. (0으로 올바르게 쪼개기 위해서)

 

그다음 소수를 구하면 된다.

소수를 구하는 방법은 아래를 참고하자.

https://smhope.tistory.com/m/175

67. 1929(소수 구하기)

def solution(n, k):
    answer = -1
    if(k==10):
        answer = prime(n)
    else:
        answer = prime(change(n, k))

10진수가 들어온다면 진수 변환을 진행하면 안되기 때문에 분기를 주었다.