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

문제 설명

• 양의 정수 n이 주어질 때, 이 숫자를 k 진수로 바꾸어 변환된 수 안에 조건에 맞는 소수(prime number)가 몇 개인지 확인
• 조건
  • P는 각 자릿수에 0(숫자)을 포함하지 않는 소수(예를 들어, 11은 가능하고 101은 불가능)
  • 0P0처럼 소수 양쪽에 0(숫자)이 있으면 안됨
  • P0 or 0P 처럼 오른쪽 혹은 왼쪽에 0(숫자)이 있으면 안됨
  • P처럼 양쪽에 아무것도 없어야 됨
• 제한 사항
  • 1 ≤ n ≤ 1,000,000
    (1에서 1백만 자리의 정수)
  • 3 ≤ k ≤ 10
    (3진수에서 10진수)
• 입출력 예시

n	k	result
437674	3	3
110011	10	2

 

문제 코드

최종 코드

- 코드 수정 사항: prime 함수에서 3 이상의 홀수에 대해서 약수가 있는지 확인하도록 수정

1차 시도

- 테스트 결과 : 문제 1번 런타임 초과

 

2차 시도

- 테스트 결과 : 테스트 통과
- 수정 사항 : prime함수에서 소수를 판별할 때, 주어진 숫자에 루트를 취해줌

 

최종 코드 풀이