https://www.acmicpc.net/problem/2814

문제

가장 작은 소인수가 P인 숫자 중에서 N번째 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 P가 주어진다. (1 ≤ N, P ≤ 10⁹) P는 항상 소수이다.

출력

첫째 줄에 가장 작은 소인수가 P인 숫자 중 N번째로 작은 수를 출력한다. 만약, 그러한 수가 10⁹를 넘을 경우에는 0을 출력한다.

풀이

백준 1557 - 제곱 ㄴㄴ 문제와 풀이 방식이 똑같다. 가장 작은 소인수가 $P$인 수를 세는 것이 아니라, 에라토스테네스의 체처럼 그렇지 않은 수를 걸러내며 푸는 것이다. 다만 이번에는 $P$보다 작은 소인수를 가지는 경우와 $P$를 소인수로 갖지 않는 경우를 모두 따져야 한다.

가장 작은 소인수가 $P$인 수는 결국 $P$의 배수이므로, 코드에 사용되는 모든 숫자를 $P$로 나누어 푼 뒤 답만 $P$를 곱하여 출력하도록 하였다. 이렇게 하면 $P$보다 작은 소인수를 가지는 경우만 따져도 된다.

어떤 수 $x$보다 작거나 같은 중 $p$의 배수의 개수는 $\left\lfloor x / p \right\rfloor$로 구할 수 있다.

소수를 미리 구해놓은 다음 포함-배제 원리를 이용해 $x$보다 작거나 같은 수 중 가장 작은 소인수가 $P$인 수의 개수를 구하는 함수 $f(x)$를 만든 뒤 $f(x-1)=N-1 \land f(x)=N$인 $x$를 이진탐색 하듯 찾는다.

이때 $x \times P > 10^9$이면 0을 출력하도록 하면 된다.

여담

• 이를 $f(10^9 / P) < n$일 때 0을 출력하도록 처리할 수도 있다.
• 가장 작은 소인수가 $P$인 첫 번째 수는 $P$, 두 번째 수는 $P^2$이다. $N=1$이면 $P$를 출력하고, 그렇지 않을 때 $P>\sqrt{10^9}=31622.7766\cdots$이면 0을 출력하도록 처리할 수 있다.