How to find no. of factors of a number in very efficient way.
1<=T<=105
1<=N<=107
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 pre-computed no. of factors for every no. But I feel this approach is slow. Can anyone suggest any modification or another approach.
Just confirming- No. of factors, or no. of prime factors?
If its number of factors, and since we are concerned with ONLY number of factors, a mathematical formula comes to help-
Let X be a number, whose prime factorization yields-
X= 2^a x 3^b x…
Then number of factors is product of (exponents +1). Meaning, number of factors are-
Number of factors= (a+1)x(b+1)…
Taking 3 examples-
17= 17 (prime factorization- 17 itself is prime)
Factors= 1+1=2. And so is the case, {1,17}
16 = 2^4
Factors = 5 ( {1,2,4,8,16})
18 = 2 * 3^2
Factors = (1+1) x (2+1) = 3x2 = 6 {1,2,3,6,9,18}
In case of doubt, feel free to ask. (Don’t ask the derivation tho…my teacher gave me this formula while studying permutation and combinations XD)
No. of factors.
if N=10 then answer would be 4
1,2,5,10
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.
Now, tell me how your approach would fit in this. Give me little idea about implementation details.
#include
#include<bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int n,i;
cin>>n;
int factors=1,exponen=0;//exponent stores power of current prime
while(n%2==0)//a separate check for 2 {
exponen++;
n=n/2;
}
factors= factors*(exponen+1);
exponen=0;
int original_n=n;
for(i=3;n>1 && i<=sqrt(original_n);i+=2)//Checking for every prime number
{
exponen=0;
while(n%i==0)
{
exponen++;
n=n/i;
}
factors= factors*(exponen+1);
}
cout<< factors<< endl;
return 0;
}
You might feel that in loop the number being checked isn’t prime. But, take case of 15, since we have already checked for its prime factors before (5 and 3), the number will give negative for 15. (we have cleaned all factors of 5 and 3, so it wont run for 15)
I hope this helps.
I didnt read ur new comment while posting answer. I will look into it if no one else answers ur Q before my next sitting. 
Shall I precompute the no. of factors for every single no. using this approach, you mean. Did you read my comment on your above answer.
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.
Take 18, for instance. The prime factors of 18 are 2 and 3; the prime factorization is 2 times 3 times 3, or (2^1)(3^2).
Consider each of 18’s factors in terms of its own prime factorization:
If you look at all of those numbers in terms of their factorizations, you’ll see every possible arrangement of 2 to the 0 or 1 power with 3 to the 0, 1, or 2 power. That’s no accident.
To generalize that method, here’s your approach:
For example find number if factors of 196:
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:
*(2^0)(7^0) = 1
(2^1)(7^0) = 2
(2^2)(7^0) = 4
(2^0)(7^1) = 7
(2^1)(7^1) = 14
(2^2)(7^1) = 28
(2^0)(7^2) = 49
(2^1)(7^2) = 98
(2^2)(7^2) = 196*
SO general approach to solving your
problem would be to find all prime
numbers upto 10^6 using sieve method
Then find prime factors of the said
numbers and their exponents
add 1 to each exponent
multiply the exponents to get the
answer
PS: If you need it coded, please request.
I did not read the comment dear ( i mentioned in my above comment) . Apologies for inconvenience. I think neil answered the Q very nicely
http://ideone.com/7HB6SB This is the code, please upvote n mark as legit answer, though vijjus code is same
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.
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
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?
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).
He needs to find greatest factor whose number of factor is of power 2, this what i understood
You can use sieve of Eratosthenes to solve this. With a small modification, you can get the smallest prime factor of every number upto N in O(N*lglgN), once this is done you can find the factorisation of any number (<=N) in O(LogN). But since you have mentioned that you just need the greatest divisor, your answer will just be the number divided by its smallest prime factor, you can do this in constant time after the sieve. Let me know (comment) if there’s something that you didn’t understand.
You can use the sieve to find the prime factorisation of the given number, suppose it is:
p1^a1 * p2^a2 * … * pk^ak, the number of factors will be (a1+1)(a2+1)…(ak+1). If you want this expression to be a power of 2, then every single term must also be a power of 2, ie. each of the ai’s must be of the form 2^k-1, so you can find the prime factorisation, find all the ai’s, and then for each ai, take as many of each as possible while making sure that its still of the form 2^k-1. Let me explain with an example:
Suppose N=60, 60 = 2^2 * 3^1 * 5^1 so the ai’s are a1=2,a2=1,a3=1. a2,a3 are equal to 2^1-1
so you can take all of them but a1 is not in the form 2^k-1, so you just take 1. So your ai’s are now 1,1,1 and the answer is (1+1)(1+1)(1+1) = 8.
As in that factor as 2^k factors, or the factor’s index is 2^k?
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.