P5946 [POI 2002] B-Smooth Numbers

$B$ is a positive integer. If a natural number $n$ is called a B-smooth number, then none of its prime factors is greater than $B$. We say that a B-smooth number equivalent to $n$ means that it can be represented as a product of positive integers less than or equal to $B$. Your task is: for the given closed interval $[n, n + m]$, find the number of B-smooth numbers in it.

The first line contains three integers $n$, $m$, and $B$.

Output the number of B-smooth numbers.

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^9$, $1 \le m \le 10^8$, $1 \le B \le 10^6$. Translated by ChatGPT 5