9821: ABC300 —— G - P-smooth number
[Creator : ]
Description
A positive integer is called a $k$-smooth number if none of its prime factors exceeds $k$.
Given an integer $N$ and a prime $P$ not exceeding $100$, find the number of $P$-smooth numbers not exceeding $N$.
Given an integer $N$ and a prime $P$ not exceeding $100$, find the number of $P$-smooth numbers not exceeding $N$.
Input
The input is given from Standard Input in the following format:
```
$N$ $P$
```
```
$N$ $P$
```
Output
Print the answer as an integer.
Constraints
- $N$ is an integer such that $1 \le N \le 10^{16}$.
- $P$ is a prime such that $2 \le P \le 100$.
- $P$ is a prime such that $2 \le P \le 100$.
Sample 1 Input
36 3
Sample 1 Output
14
The 3-smooth numbers not exceeding 36 are the following 14 integers: 1,2,3,4,6,8,9,12,16,18,24,27,32,36.
Note that 1 is a k-smooth number for all primes k.
Note that 1 is a k-smooth number for all primes k.
Sample 2 Input
10000000000000000 97
Sample 2 Output
2345134674