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
David: 2021-03-19 23:15:23

@faraday_vij Each individual test case has a time limit of 1.0 seconds. Your time for this problem is the sum of all test cases.

onkar_telange: 2020-10-02 23:05:46

Long gives tle but for int AC. Why this?

Shubham Jadhav: 2020-07-12 20:53:19

beauty

faraday_vij: 2020-03-17 19:28:55

my code is showing that running time is 12.65 seconds and my solution got accepted.
but the actual time limit is 1 sec. then how the hell did my solution got accepted ??
and some best solutions passed in 0.00 sec. how is this even possible?
at least it should take some nominal time for finding the prime numbers naa!!

scolar_fuad: 2019-07-20 15:04:14

Efficiet seive give you best optimization

Time limit :0.70ms

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
hottest: 2018-01-12 11:50:52

using long gives tle,int gives ac

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

AC 0.00 s!!!

Last edit: 2018-08-15 19:23:17
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).


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