[Python] 2022 KAKAO BLIND RECRUITMENT : k진수에서 소수 구하기

2022 KAKAO BLIND RECRUITMENT : k진수에서 소수 구하기

문제풀이

P의 조건을 되게 복잡하게 설명해 놨지만 사실상 결론적으론 되게 간단하다.
0 사이에 있는 숫자들이 소수인지, 아닌지만 구분하면 되는 것이다.
1. 주어진 n을 k진수로 변경한다.
1-1. n을 k로 나누었을 때 나머지를 제일 앞자리에 추가해준다.
ex) num = str(n%k) + num
1-2. n은 k로 나눈 몫이 된다.
ex) n = n // k
1-3. n이 0이 될 때까지 이 과정을 반복해준다.
ex) while n:
2. k진수로 변경한 수를 "0"을 기준으로 나눈다.
ex) nums.split("0")
3. nums에 담긴 숫자들이 소수인지 판단하여 개수를 구한다.

• 기초적인 방식으로 소수인지 판단할 경우 효율성에서 통과하지 못하므로, 범위를 2부터 n의 제곱근까지 검사하는 방식으로 하여야 한다.

답

#문제 풀이 1번
def binary(n,k):
    num = ""
    while n:
        num = str(n%k) + num
        n = n // k
    return str(num)
def solution(n, k):
    answer = 0
    nums = binary(n,k)

    nums = nums.split("0") # 문제 풀이 2번
# 문제 풀이 3번
    for num in nums:
        if len(num) == 0:
            continue
        if int(num) < 2:
            continue
        sosu = True
        for i in range(2, int(int(num)**0.5)+1):
            if int(num)%i == 0:
                sosu = False
        if sosu:
            answer += 1

    return answer