Score : $600$ points

问题描述

一个正整数被称为 $k$-光滑数，如果它的所有质因数都不超过 $k$。

给定一个整数 $N$ 和不超过 $100$ 的质数 $P$，求不超过 $N$ 的 $P$-光滑数的数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

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$.

Constraints

• $N$ is an integer such that $1 \le N \le 10^{16}$.
• $P$ is a prime such that $2 \le P \le 100$.

Input

The input is given from Standard Input in the following format:

$N$ $P$

Output

Print the answer as an integer.

Sample Input 1

36 3

Sample Output 1

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$.

Sample Input 2

10000000000000000 97

Sample Output 2

2345134674

update @ 2024/3/10 08:24:56