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

[vijju123]

Nice catch.

I missed the case where N gets reduced to a prime number after division by 2. It was written when I was very new here so pardon me xD. For that case, we need to multiply it by 2.

[rithiksingh098]

this is my code to find the number of divisors of any number including 1 and n

Ideone.com

#include <bits/stdc++.h>
using namespace std;

int process(int n)
{
	int ex=1;
	long long ans=1;

		while(!(n%2)){
			n/=2;
			ex++;
		}

	ans=ans*(ex);
	for(int i=3;i*i<=n;i+=2){//we will go till root(n) only as after that only one prime would be left or 1

			ex=1;
			while(!(n%i)){
				n/=i;
				ex++;
				//push I if you want all the primes
			}
			ans*=(ex);

	}
	if(n>1) ans*=2;
	//push n if you want all the prime factors
	return ans;
}
int main()
{
    int n;cin>>n;
    cout<<process(n);
}

Please let me know if its correct.

[rithiksingh098]

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); } if(n>1)factors*=2; cout<< factors<< endl; return 0; }

@vijju123
My code is different from your code by just one line! but I think both our codes are correct(my being faster)

int original_n=n; you have used orginal n after removing the powers of 2
and I am using the modified n after every iteration
but still for all test cases the answers are same…

I think because after every for loop the question becomes find the number of divisors for n with removed powers of the previous prime.

If I am not wrong my code would be faster than yours

[vijju123]

Perhaps, but I think that the time complexity of both our codes are same. I dont mind constant factors much

[salil03]

The derivation is easy.

Suppose the number is p = a^x \times b^y \times c^z...

Every factor of this number should atleast have some power of a or b or c or ...
There are total x+1 powers of a (including a^0)
There are total y+1 powers of b (including b^0)
There are total z+1 powers of c (including c^0)
.
.
.

So total ways to choose a factor are (x+1)\times(y+1)\times(z+1)...
QED