×

# what is the most efficient way to find no. of factors of a number?

 0 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. asked 08 Apr '17, 19:30 1★arpit728 683●15●62 accept rate: 10% Just confirming- No. of factors, or no. of prime factors? (08 Apr '17, 19:37) No. of factors. if N=10 then answer would be 4 1,2,5,10 (08 Apr '17, 19:42) arpit7281★

 1 #include #include 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. answered 08 Apr '17, 20:35 15.2k●1●18●59 accept rate: 18% 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. :) (08 Apr '17, 20:41) @vijju123 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. (08 Apr '17, 20:41) arpit7281★ 1 I did not read the comment dear ( i mentioned in my above comment) . Apologies for inconvenience. I think neil answered the Q very nicely :) (08 Apr '17, 21:01)
 2 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) answered 08 Apr '17, 19:42 15.2k●1●18●59 accept rate: 18% 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. (08 Apr '17, 20:05) arpit7281★
 1 @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&(k-1))==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 k-1 would be of the form(111111). Performing bitwise and on these numbers yields 0. answered 10 Apr '17, 10:31 61●1 accept rate: 33% 1 Thank you for this optimization trick, though I knew it but it didn't click then. (10 Apr '17, 11:38)
 0 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. answered 09 Apr '17, 01:05 1.4k●11 accept rate: 28% @hemanth_1 I actually need to find no. of factors of the any factor of N such that no. of factors should be maximized and also no of factors should be power of 2. (09 Apr '17, 07:34) arpit7281★ @hemanth_1 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:34) arpit7281★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,650
×625
×300
×30

question asked: 08 Apr '17, 19:30

question was seen: 4,979 times

last updated: 10 Apr '17, 11:38