How to find no. of factors of a number in very efficient way. 1<=T<=10^{5} 1<=N<=10^{7} Given a no. of test cases T and for each case there is one line of input which represents an integer N. For each case output no. of factors of N. MY APPROACH This is my approach, I have precomputed no. of factors for every no. But I feel this approach is slow. Can anyone suggest any modification or another approach. asked 08 Apr '17, 19:30

The concept behind this method is that the prime factorization of a number determines all of its factors. If a number is divisible by 2, for instance, 2 will be a factor of many of the number's factors. In fact, each factor of a number is built up of one or more of the number's other factors.
There are 9 factors of 196. To see what those are, work through the permutations of the exponents 0, 1, and 2 for the prime factors 2 and 7:
answered 08 Apr '17, 20:42
If possible code would be really appreciated.
(08 Apr '17, 21:59)
http://ideone.com/7HB6SB This is the code, please upvote n mark as legit answer, though vijjus code is same
(08 Apr '17, 22:47)
Let me tell you the complete question. I actually Want to find greatest factor of number whose no. of factors is power of 2. So what I was doing is for each no. I precomputed no. of factors then I looped for(i=n;i>0;i) and if (i%n==0) then I checked if i is power of 2 is yes then returned i otherwise complete the loop.
(09 Apr '17, 00:00)
This is link to my code, please tell me how I can improve it. I am not getting accepted with this code. I am getting TLE. Please help me out @neilit1992 @vijju123
(09 Apr '17, 00:21)
In your code you can change solve part from i=1 to n^(1/2) and factor are usually of form i and n/i so if 2 is factor of 12 12/2 = 6 is also a factor of 12 so you can reduce the solve part to O(n^(1/2) time complexity and to count factors better use my code, its efficient than your naive algo, and I couldn't get why you are using initfactor method?
(09 Apr '17, 00:35)
Wait...i didn't understand. You have to find the greatest factor which is power of 2? Then well...isn't 2^x the answer (where x is exponent we calculated above)? Any link to Q? And if the Q is to find greatest factor, then also, nothing complicated. First check if number prime or not (Sieve might help), check if I%2==0. If yes, then I/2 s greatest factor. If no, check I%3,i%5,i%7..all primes. We can mathematically prove that if I%n==0 (from start). then I/n is greatest factor (for first n enocountered as such).
(09 Apr '17, 00:55)
He needs to find greatest factor whose number of factor is of power 2, this what i understood
(09 Apr '17, 01:02)
As in that factor as 2^k factors, or the factor's index is 2^k?
(09 Apr '17, 02:08)
for n=15 ans=4 for n=48 ans=8 for n=60 ans=8 for n=15 factors are {1,3,5,15} i.e, 4 factors which is power of 2 so the answer is 4. for n=48 factors are {1,2,3,4,6,8,12,16,24,48} i.e 10 factors in total which is not power of 2. But the factor of 24 has 8 factors which is power of 2, so the o/p is 8 fir second test case. for n=60 factors are {1,2,3,4,5,6,12,15,20,30,60}i., 11 factors in total which is not power of 2 but the factor of 30 has 8 factors in total which is power of 2 so the answer is 8. I think it makes point clear, if you still don't understand, please write.
(09 Apr '17, 07:30)
in initFactors() I am precomputing smallest prime factor for every no. and this helps me to count no. of factors efficiently. and I think for counting factors I think runtime of my algorithm is as good as yours if you observe closely. May be I am wrong.
(09 Apr '17, 07:49)
I have coded an efficient algo, http://ideone.com/7HB6SB If you can provide me link to the question it would be better, anyway check it..
(09 Apr '17, 11:27)
Can you brief, what exactly you are doing.
(09 Apr '17, 12:00)
http://ideone.com/7HB6SB I have commented the code, upvote the ans, and mark as correct Thank you, if you need further clarification request
(09 Apr '17, 12:16)
I understand your code and logic but can you please tell how complexity of your code is better than that of mine. I feel complexity of my code is same as that of yours. This is final version of my code. http://ideone.com/SCF7NM
(09 Apr '17, 13:22)
Run my code and see whether it gets AC or not, I feel you are using initfactor for no reason, when you can calculate number of factors without actually storing the factors, why do you need to store it at all? Better provide link to the problem
(09 Apr '17, 13:30)
1
Thanks Buddy, I got AC. It has been really great effort by you thank you so much.
(09 Apr '17, 14:47)
why have you multiplied ans by 2 in the end of process function.
(09 Apr '17, 14:53)
if n is >1 that means n is prime, otherwise it isn't, so if n is prime I'm multiplying it by 2, because a prime number has 2 factor 1 and itself, if it isn't prime it will reduce to 1 by the end of loop, coz i divide n at each step. You can simulate this process on some prime number to better understand the underlying concept.
(09 Apr '17, 15:24)
I am sorry, I was kind of busy today. I saw your comment now, and I think neil has answered it nicely. In case you feel I can be of service, comment/mail me. (But I wont be able to help until evening, I am kind of stuck atm) Thanks.
(09 Apr '17, 15:51)
showing 5 of 20
show all

@arpit728 @neilit1992 function for checking if a no is a power of 2 can be further optimised bool powerof2(int k) { if((k!=0)&&((k&(k1))==0)) return 1; return 0; } It can be explained by writing a no in its binary form. A number k which is a power of 2(eg 64) has only its leftmost bit set(1000000) whereas k1 would be of the form(111111). Performing bitwise and on these numbers yields 0. answered 10 Apr '17, 10:31
1
Thank you for this optimization trick, though I knew it but it didn't click then.
(10 Apr '17, 11:38)

Just confirming No. of factors, or no. of prime factors?
No. of factors. if N=10 then answer would be 4
1,2,5,10