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

소스코드

def solution(n, k):
    changedNum = ''
    checkPrime = ''
    answer = 0
    while n != 0 :
        changedNum += str(n%k)
        n = n//k     
    changedNum = changedNum[::-1].split('0')
    for i in (changedNum):
        if i != '':
            if isPrime(int(i)):
                answer += 1
    return answer

def isPrime(number):    

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

 

---

알고리즘

문제를 나눠보면 다음과 같이 2개만 구현하면 된다.

1. k진수로 변환

2. 소수인지 체크

 

1. k진수 변환

나머지를 나눠가며 갱신을 해주고 마지막에 reverse 해준다. 

ex) 11 -> 3일때

나머지 = 2, 몫 = 3

나머지 = 0, 몫 = 1

하면 201인데 reverse 해줘야하니깐 :)

 

2. 소수인지 체크

그런 다음 0을 기준으로 숫자를 소수 판별을 해야하므로 split('0')함수를 써서 리스트로 만들어준다.

그러면 '201' -> ['2','1'] 이렇게 된다.

그런 다음 소수 판별 함수 적용해주면 된다.

 

3. 소수 판별 함수

11, 15,16,17 문제가 틀리는 사람들은 소수 판별함수 다시 작성해야한다.