P의 조건을 되게 복잡하게 설명해 놨지만 사실상 결론적으론 되게 간단하다.
0 사이에 있는 숫자들이 소수인지, 아닌지만 구분하면 되는 것이다.
1. 주어진 n을 k진수로 변경한다.
1-1. n을 k로 나누었을 때 나머지를 제일 앞자리에 추가해준다.
ex) num = str(n%k) + num
1-2. n은 k로 나눈 몫이 된다.
ex) n = n // k
1-3. n이 0이 될 때까지 이 과정을 반복해준다.
ex) while n:
2. k진수로 변경한 수를 "0"을 기준으로 나눈다.
ex) nums.split("0")
3. nums에 담긴 숫자들이 소수인지 판단하여 개수를 구한다.
- 기초적인 방식으로 소수인지 판단할 경우 효율성에서 통과하지 못하므로, 범위를 2부터 n의 제곱근까지 검사하는 방식으로 하여야 한다.
#문제 풀이 1번 def binary(n,k): num = "" while n: num = str(n%k) + num n = n // k return str(num) def solution(n, k): answer = 0 nums = binary(n,k) nums = nums.split("0") # 문제 풀이 2번 # 문제 풀이 3번 for num in nums: if len(num) == 0: continue if int(num) < 2: continue sosu = True for i in range(2, int(int(num)**0.5)+1): if int(num)%i == 0: sosu = False if sosu: answer += 1 return answer