NFACTOR - N-Factorful
A number is called n-factorful if it has exactly n distinct prime factors. Given positive integers a, b, and n, your task is to find the number of integers between a and b, inclusive, that are n-factorful. We consider 1 to be 0-factorful.
Input
Your input will consist of a single integer T followed by a newline and T test cases. Each test case consists of a single line containing integers a, b, and n as described above.
T > 10000
1 ≤ a ≤ b ≤ 106
0 ≤ n ≤ 10
Output
Output for each test case one line containing the number of n-factorful integers in [a, b].
Example
Input: 5 1 3 1 1 10 2 1 10 3 1 100 3 1 1000 0 Output: 2 2 0 8 1
hide comments
kartikay singh:
2015-05-30 21:50:40
AC with 0.09s :) Last edit: 2015-05-30 21:52:21 |
|
Madhav:
2015-03-24 11:07:31
A great problem...Many concepts involved.... |
|
sparrow:
2015-01-17 16:11:23
nice problem....
|
|
John and the cows:
2014-08-26 18:52:15
well, it's seem there are more than 10^5 test cases |
|
JordanBelfort:
2014-03-17 21:15:11
no binary search think simple |
|
harsh:
2014-01-20 06:10:25
binary_search()..:). |
|
shuvo karmakar:
2013-12-18 21:07:55
0 |
|
cegprakash:
2013-12-12 20:38:38
A must do. Superb problem! |
|
demon:
2013-09-23 17:27:28
Good one :) |
Added by: | periclesmachado |
Date: | 2011-01-30 |
Time limit: | 1.879s-2.484s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Facebook Hacker Cup 2011 Round 1C |