1623: Smooth Numbers
内存限制:128 MB
时间限制:90.000 S
评测方式:文本比较
命题人:
提交:3
解决:1
题目描述
A positive integer is said to be k-smooth if its largest prime factor is no greater than k. Compute how many positive integers less than or equal to N are k-smooth.
输入
The input will contain one case.
The first line contains two integers N (1 ≤ N ≤ 5,000,000), k (1 ≤ k ≤ 1000).
输出
Output one integer on a line, representing how many positive integers less than or equal to N are k-smooth.
样例输入 复制
Case 1:
10 3
Case 2:
10 4
Case 3:
15 3
Case 4:
5 20
Case 5:
123456 123
样例输出 复制
Case 1:
7
Case 2:
7
Case 3:
8
Case 4:
5
Case 5:
23855
提示
Case 1: Of the first ten positive integers, only 5, 7 and 10 have prime factors greater than 3; the rest are 3-smooth.
Case 2: 4 is not prime, so 4-smooth numbers are the same as 3-smooth numbers.