SPOJ.com - Problem NDIV

NDIV - n-divisors

#number-theory #sieve

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⁹
0 ≤ b - a ≤ 10⁴
1 ≤ n ≤ 100

Submit solution!

hide comments

< Previous 1 2 3 Next >

	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
	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
	P_Quantum: 2014-07-02 09:55:05 nice!!
	hossamyosef: 2014-04-25 01:37:51 I think the output should be the number of mistakes on the problem statement. :v :v (abdelkarim) i think you can talk about the problem statement after solving the problem it self :P Last edit: 2014-04-25 01:20:58
	Priyanshu Srivastava: 2014-04-25 01:37:51 0.01 s....Top of the table.. :D Last edit: 2013-08-28 07:03:13

Submit solution!

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