[알고리즘] 프로그래머스 - k진수에서 소수 개수 구하기

문제

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

프로그래머스

 

풀이

단순 구현으로 풀었다. 예전에도 풀었던 문제라서...! 특정 진수로 변환하는 법을 까먹어서 검색해서 풀었다.. ㅎ 기억 좀 하자

현재 숫자를 원하는 진수로 나눈 나머지 값을 str형태로 넣어주고 n은 해당 진수로 나눈 몫으로 바꾼다. n이 있을 때까지 반복 ... => 그렇게 탄생한 str을 거꾸로 돌려주면 원하는 진수로 변환된 값이 나옴!

당연하지만 소수인지 확인할 땐 1부터 해당 숫자까지 for문을 돌리면서 나머지 확인하지 말고 제곱근(sqrt)+1 까지만 돌려주면 된다.

 

 

코드

import math
def solution(n, k):
    answer = 0
    
    if k==10:
        num=str(n)
    else:
        tmp = ''
        while n:
            tmp += str(n % k)
            n = n // k

        num=tmp[::-1]
    
    new_list=list(num.split('0'))
    for i in new_list:
        tmp_num=0
        if i=='':
            continue
        for j in range(2,int(math.sqrt(int(i))) + 1):
            if int(i)%j==0:
                tmp_num+=1
            if tmp_num>2:
                break
        if i!='1' and tmp_num==0:
            answer+=1
    
    
    return answer