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
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

harshgupta007: 2016-12-26 16:38:55

made a lot of mistakes trying a lot of different algorithms, finally got AC

karan_batra: 2016-08-28 15:31:07

Easy one. AC in one go :D.

insanshuman: 2016-08-09 20:56:22

ideone time limit:0.01s
but here time limit exceeded is shown
why?

Ankur Singh: 2014-10-08 20:28:05

how is top solution made?
time: 0.01 sec!!!

Shivam Mitra: 2014-08-29 00:39:32

Nice question.Teaches two efficient algorithms.

THE_SCORPION: 2014-08-22 23:10:47

TLE in test 22 any help ??

(reply by cyclops) Judging does not halt on first failure. This means that if you see "Running... (22)", you cannot assume your code was correct and fast enough for 0 through 21. For debugging help, you may find the forum useful.

Last edit: 2014-08-22 23:39:21

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