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

general
, , ,
21

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

22

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

23

@neilit1992

in initFactors() I am precomputing smallest prime factor for every no. and this helps me to count no. of factors efficiently. and I think for counting factors I think runtime of my algorithm is as good as yours if you observe closely. May be I am wrong.

24

I have coded an efficient algo, http://ideone.com/7HB6SB If you can provide me link to the question it would be better, anyway check itā€¦

25

@neilit1992

Can you brief, what exactly you are doing.

26

http://ideone.com/7HB6SB I have commented the code, upvote the ans, and mark as correct Thank you, if you need further clarification request

27

@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. http://ideone.com/SCF7NM

28

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

29

@neilit1992

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

1 Like
30

@neilit1992

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

31

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.

32

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.

33

@vijju123

Thanks a lot, my problem is solved.

1 Like
34

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

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

1 Like