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
enigma_112:
2020-03-03 23:04:09
AC in one attempt :) |
|
tanav_shah1:
2019-11-05 21:13:39
Excellent question!!! Great use of sieve.
|
|
aayush_b1999:
2019-07-18 19:30:49
@rajat813 these are the 6 integers
|
|
rajat813:
2019-03-14 00:45:51
how answer of
|
|
ameyanator:
2018-03-22 23:05:44
I've got a O(T+(X*root(X)) approach where X=10^6. Used preprocessing memoization. I've got an AC @1.18 secs but I see people with quite less runtimes ~<0.5secs. Whats the approach for it? |
|
jh0n_12358:
2017-12-04 07:38:29
AC in one go
|
|
sas1905:
2017-06-16 21:47:54
Sieve + BIT ..:) |
|
stranger77:
2017-05-28 03:05:13
AC in 0.06 sec .......use upper & lower bound stl....... |
|
shahzada:
2017-03-01 08:44:22
Just Precomputation. |
|
holmesherlock:
2017-01-24 16:35:36
tle at first but then precomputation came to rescue..:)
|
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 |