[Poi2002]B-Smooth 数

时间限制:10s      空间限制:128MB

题目描述

 
B 是一个正整数. 如果一个自然数n 被称为B-smooth数,那么它的质因素中没有任何一个超过B. 我们说和n等价的一个B-smooth数, 如果它能够表示成小于或等于B的正整数乘积。 你的任务是对给定的闭区间[n,n+m],求出他们中的B-smooth数的个数。


输入格式

第一行有用单个空格分隔的三个整数n, mB, 1<=n<=2 000 000 000, 1<=m<=100 000 000, 1<=B<=1 000 000.


输出格式

求出B-smooth数的个数.


样例输入

30 10 5



样例输出

4

提示

没有写明提示


题目来源

没有写明来源