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

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.

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)

4 Likes

#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.

3 Likes

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:

  • 1 = (2^0)(3^0)
  • 2 = (2^1)(3^0)
  • 3 = (2^0)(3^1)
  • 6 = (2^1)(3^1)
  • 9 = (2^0)(3^2)
  • 18 = (2^1)(3^2)

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:

  • Find the prime factorization of a
    number (each one of the number’s
    prime factors raised to the
    appropriate power).
  • List all of the exponents.
  • Add one to each of the exponents.
    (Remember, it’s possible to raise the
    prime factor to the zero power.)
  • Multiply the resulting numbers.

For example find number if factors of 196:

  • The prime factorization: 196 =
    (2^2)(7^2)
  • The powers: 2 and 2
  • Add one to the powers: 3 and 3
  • Multiply the results: (3)(3) = 9

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.

3 Likes

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.

1 Like

@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.

1 Like

Just confirming- No. of factors, or no. of prime factors?

1 Like

No. of factors.
if N=10 then answer would be 4

1,2,5,10

@vijju123

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.

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. :slight_smile:

@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.

I did not read the comment dear ( i mentioned in my above comment) . Apologies for inconvenience. I think neil answered the Q very nicely :slight_smile:

1 Like

@neilit1992

If possible code would be really appreciated.

7HB6SB - Online C++0x Compiler & Debugging Tool - Ideone.com This is the code, please upvote n mark as legit answer, though vijjus code is same

1 Like

@neilit1992

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.

@neilit1992

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

As in that factor as 2^k factors, or the factor’s index is 2^k?