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

문제

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

n: 양의 정수 (1 ≤ n ≤ 1,000,000)
k: 진수 (3 ≤ k ≤ 10)

n을 k진수로 표현했을 때 찾을 수 있는 소수의 개수를 구하는 문제.
조건에 맞는 소수 p를 찾으라고 했는데 결국 0을 기준으로 나누었을 때 표현 가능한 소수의 개수를 구하는 문제이다.

풀이

1. 주어진 n을 k로 나눈다
2. 나머지가 0이라면, 스택에 있는 값들로 숫자를 만든다.
   • 스택에 있는 값들로 만든 숫자가 소수일 경우 count 증가
3. 나머지가 0이 아니라면, 스택에 나머지를 push한다.
4. 몫을 n으로 바꾼 후 1-3 과정을 n이 0이 될 때까지 반복한다.

소수 판별 과정에서 1~(num의 제곱근)까지만 판별해주면 되고, stack을 통해 만들어진 숫자의 크기가 int 범위를 넘어설 수 있어 long long 자료형을 사용해주어야 한다.

코드

https://github.com/LGY010011/Algorithm/blob/main/Algorithm/P92335.cpp