[프로그래머스]k진수에서 소수 개수 구하기(파이썬) -카카오 인턴쉽 기출

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

프로그래머스

구현+수학이 들어간 문제.

 

먼저, 정수n을 k진법으로 바꾼다.

그 다음, 0이 나올때까지 숫자를 넣어주고

0을 만나면 그 숫자가 소수인지 판별해준다.

만약에 숫자가 남아있는데 진법으로 변환된 수를 다 돌았다면

그 숫자가 소수인지 판별해준다.

 

여기서 주의할 점은 소수판별법입니다.

2~제곱근+1한 값까지 나눴을때만을 구해야

시간초과를 피할 수 있습니다.

import math

def prime(n):
    if n==1:
        return False
    for x in range(2, int(math.sqrt(n)+1)):
        if n % x == 0:
            return False

    return True


def solution(n, k):
    answer = 0
    change_num = ''
    #1 k진법으로 변환
    while n >= 1:
        ap = n % k
        change_num = str(ap) + change_num
        n //= k

    now = ''
    #숫자를 돌면서 숫자 받아보기
    for i in range(len(change_num)):
        n_num = int(change_num[i])
        #0이 아니라면 숫자를 더해준다
        if n_num != 0:
            now += change_num[i]
        #0을 만나면-->소수인지 판별
        else:
            if now!='':
                new = int(now)
                now = ''
                if prime(new):

                    answer += 1
    #만약 숫자가 남아있다-->판별해주기
    if now!='':
        if prime(int(now)):
            answer+=1
    return answer

 

수학도 공부해보고

구현공부도 해볼 수 있는 좋은 문제였습니다.

개인적으로 소수판별은 익혀두면 편할 것 같네요.

(워낙 많이 나오는 유형이기도 하고

정리해두면 나중에

시간초과에서 자유로울듯하니

소수판별은 닥치고 외우는 것도 좋아보이네요)