Polish version    English version  
  History of OI -> IX OI 2001/2002


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Rules
For contestants
Helpful resources
Stats
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
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 5
the correct answer is in the following output file lic.out:
4



Print friendly version