NDIV - n-divisors


We all know about prime numbers, prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

We can Classify the numbers by its number of divisors, as n-divisors-numbers, for example number 1 is 1-divisor number, number 4 is 3-divisors-number... etc.

Note: All prime numbers are 2-divisors numbers.

Example:
8 is a 4-divisors-number [1, 2, 4, 8].

Input

Three integers a, b, n.

Output

Print single line the number of n-divisors numbers between a and b inclusive.

Example

Input:
1 7 2

Output:
4

Constraints

1 <= a, b <=10^9
0 <= b - a <= 10^4
1 <= n <= 100


hide comments
gargmehul10: 2018-03-23 12:19:30

Without using sieve { doing prime factorization in sqrt(n) }, long gives TLE but int gives AC! How ???

Last edit: 2018-03-23 12:26:21
beastgmr: 2018-03-22 07:35:47

Last edit: 2018-03-22 07:37:32
hottest: 2018-01-12 11:50:52

using long gives tle,int gives ac

vishwanath_26: 2017-08-30 14:58:22

4 RE due to including unnecessary test case!!
Finally AC 0.00 s!!!

Last edit: 2017-08-30 14:59:50
amulyagaur: 2017-07-21 21:23:34

0.00 s with segmented sieve for divisors

sam128: 2017-07-10 21:05:22

use fast i/o for this problem..also sieving must be done till sqrt(10^9).

luvk1412: 2017-05-26 02:23:59

AC in 1 go, nice question, 0.00 sec :D

mastik5h_1998: 2017-03-21 17:20:25

strict time limit but AC...

scorpion_ajay: 2017-01-08 04:22:50

this is an easy one if you understand the concept of prime factorization and sieve :)

awesomeabhinav: 2017-01-01 18:02:32

I m getting TLE, I think my solution is efficient. PLEASE HELP
Solution id 18492490


Added by:abdelkarim
Date:2012-12-07
Time limit:0.221s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Owner