![[naglowek]](hdr00008.gif)
|
IX Olimpiada Informatyczna 2001/2002
|
|
Task: lic
|
Author: Wojciech Guzicki
|
B-Smooth Numbers
| III stage contest |
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 5the correct answer is in the following output file lic.out:
4