A62495 | factorization【问题描述】Adleman非常喜欢数学，最近他遇到了一个棘手的问题：对于一个正整数A，Adleman发现一些自然数的质因子分解式中没有大于A的因子，这样的自然数非常的特殊。Adleman想知道对于给定的正整数A，一个区间[N, N+M]内所有满足上述条件的自然数的个数。【输入说明】第一行：3个用空格分开的整数N、M、A。【输出说明】第一行：一个整数，表示对于给定的正整数…

factorization

【问题描述】

Adleman非常喜欢数学，最近他遇到了一个棘手的问题：

对于一个正整数A，Adleman发现一些自然数的质因子分解式中没有大于A的因子，这样的自然数非常的特殊。Adleman想知道对于给定的正整数A，一个区间[N, N+M]内所有满足上述条件的自然数的个数。

【输入说明】

第一行：3个用空格分开的整数N、M、A。

【输出说明】

第一行：一个整数，表示对于给定的正整数A，区间[N, N+M]内特殊自然数的个数。

【样例输入】

30 10 5

【样例输出】

4

【样例解释】

[30, 40]之间的数质因子分解式如下：

30=2*3*5

31=1*31

32=2*2*2*2*2

33=3*11

34=2*17

35=5*7

36=2*2*3*3

37=1*37

38=2*19

39=3*13

40=2*2*2*5

其中30、32、36、40的质因子分解式中没有大于5的因子，所以一共有4个。

【数据范围】

50%的数据满足：1≤N,M,A≤5000

100%的数据满足：1≤N,M,A≤50,000