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

general
, , ,
26

@neilit1992

Can you brief, what exactly you are doing.

27

7HB6SB - Online C++0x Compiler & Debugging Tool - Ideone.com I have commented the code, upvote the ans, and mark as correct Thank you, if you need further clarification request

2 Likes
28

@neilit1992

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. SCF7NM - Online Java Compiler & Debugging Tool - Ideone.com

29

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

30

@neilit1992

Thanks Buddy, I got AC. It has been really great effort by you thank you so much.

1 Like
31

@neilit1992

why have you multiplied ans by 2 in the end of process function.

32

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.

33

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.

34

@vijju123

Thanks a lot, my problem is solved.

1 Like
35

Thank you for this optimization trick, though I knew it but it didn’t click then.

1 Like
36

Why is the power of 2 precomputed and not for other prime numbers?

37

here u go : https://www.hitbullseye.com/Quant/Factors-Number.php

38

For 10 your output is 2
it should be 4
10 has factors 1 2 5 10

39

here u go
10 = 2(power 1) X 5(power 1)
no. of factors = (1+1)*(1+1) = 2 * 2 = 4

40

why is your code giving 3 as output for 12???

41

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.

1 Like
42

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

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

1 Like
43

@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

44

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

45

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