|
IX Olimpiada Informatyczna 2001/2002
|
|
Task: lic
|
Author: Wojciech Guzicki
|
B-Smooth Numbers
Let B be a positive integer. A natural number n is
called B-smooth, if in its factorisation into primes there is
no prime factor greater then B. We may say equivalently that a
number n is called B-smooth, if it may be represented as
a product of positive integers less then or equal to B.
Task
Write a program which:
- reads from the text file lic.in three positive integers
n, m and B,
- determines the number of all B-smooth numbers in the
interval [n,n+m] (inclusive),
- writes the result to the text file lic.out.
Input
In the first line of the text file lic.in there are three
integers n, m and B, separated by single spaces,
1<=n<=2 000 000 000,
1<=m<=100 000 000,
1<=B<=1 000 000.
Output
Your program should write one integer in the first line of the text
file lic.out. It should be the determined number of
B-smooth numbers.
Example
For the following input file lic.in:
30 10 5
the correct answer is in the following output file lic.out:
4