P8084 [COCI 2011/2012 #4] BROJ

Find the $N$-th smallest positive integer not exceeding $10^9$ whose smallest prime factor is $P$.

The first line contains two integers $N, P$. It is guaranteed that $P$ is a prime number.

Output the required $N$-th smallest positive integer not exceeding $10^9$. If the answer exceeds $10^9$, output $0$.

**【Constraints and Notes】** - For $30\%$ of the testdata, the output is less than $10^5$ (including $0$). - For another $30\%$ of the testdata, $P \gt 1000$. - For $100\%$ of the testdata, $1 \le N, P \le 10^9$. **【Hints and Explanation】** **This problem is translated from [COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #4](https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf) _Task 5 BROJ_.** **The score of this problem follows the original COCI setting, with a full score of $140$.** Translated by ChatGPT 5