[프로그래머스] k진수에서 소수 개수 구하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

1. 소수 판별을 할 때 반복을 줄이기 위해 해당 수의 제곱근까지만 반복하는데 이때 sqrt() 함수를 사용하기 위해 math 모듈을 불러온다. import math
2. 해당 수를 해당 진법으로 바꾼 결과를 저장할 리스트를 생성한다. result = list()
3. 해당 수가 0이 되기 전까지 반복하며 while (n > 0)
4. 해당 수를 진법으로 나눈 나머지를 문자열 형태로 추가하고 result.append(str(n % k))
5. 해당 수를 진법으로 나눈 몫의 결과로 다시 저장한다. n //= k
6. 진법으로 바꾼 결과는 거꾸로 저장되어 있으므로 뒤집어 준다. result.reverse()
7. 바꾼 결과를 하나의 문자열로 합치고 result = ''.join(result)
8. 0을 기준으로 다시 분리한다. result = result.split('0')
9. 분리한 결과를 하나씩 추출하여 for i in result
10. 만약 추출한 문자열이 공백이 아니고 1이 아니면 if (i != '') and (int(i) != 1)
11. 소수인지 저장할 변수를 생성하고 초기화한다. check = True
12. 2부터 판별할 수의 제곱근까지 반복하며 for j in range(2, int(math.sqrt(int(i))) + 1)
13. 만약 해당 수가 나누어 떨어지면 if (int(i) % j == 0)
14. 소수가 아니므로 소수가 아니라고 판별한다. check = False
15. 소수가 아닌 것으로 판별되었으므로 판별을 종료한다. break
16. 판별을 마친 뒤, 소수이면 소수 개수를 1 증가시킨다. if (check): answer += 1

반응형

3. 소스코드

import math 

def solution(n, k):
    answer = 0
    
    result = list()
    while (n > 0):
        result.append(str(n % k))
        n //= k
        
    result.reverse()
    result = ''.join(result)
    result = result.split('0')

    for i in result:
        if (i != '') and (int(i) != 1):
            check = True
            for j in range(2, int(math.sqrt(int(i))) + 1):
                if (int(i) % j == 0):
                    check = False
                    break

            if (check):
                answer += 1
        
    return answer