Ram is a bright boy who is very much interested in number theory. He was studying about factorials of numbers , and got some interesting idea.
Being a brilliant coder, he started writing a program and implemented the following routines :
fact(n) -- This function returns the value of n! , where n>=0
eg. fact(5) returns 120
count(n) -- This function returns the number of terms in the prime factorisation of n , where n>=0.
eg. count(24) returns 4 (because , 24 = 2*2*2*3). The prime factorisation of 24 contains 4 terms
func(n) – This function is explained below.
Ram wrote the function “func” as follows:
int func(int n) {
int ans = 0;
for(int i=0; ; i++) {
if(count( fact( i ) ) <= n)
ans++;
else
return ans;
}
}
The above procedure takes too much time to execute. Help Ram by writing a more efficient solution that does the same function as “func” does.
The first line of input gives the number of test cases "t".
The next "t" lines contains a positive integer, representing "n".
1 <= t <= 1000
1 <= n <= 20000000
Print func(n) for the given "n", on a line by itself.
4 1 2 3 4
3 4 4 5
Migrated from old NTUJ.
UVA 11415
| No. | Testdata Range | Score |
|---|