You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 08 Apr '17, 19:30

arpit728's gravatar image

1★arpit728
6831562
accept rate: 10%

edited 08 Apr '17, 19:33

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

(08 Apr '17, 19:37) vijju123 ♦♦4★

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

1,2,5,10

(08 Apr '17, 19:42) arpit7281★

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

answered 08 Apr '17, 20:42

neilit1992's gravatar image

3★neilit1992
1.1k13
accept rate: 20%

edited 08 Apr '17, 20:50

@neilit1992

If possible code would be really appreciated.

(08 Apr '17, 21:59) arpit7281★

http://ideone.com/7HB6SB This is the code, please upvote n mark as legit answer, though vijjus code is same

(08 Apr '17, 22:47) neilit19923★

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

(09 Apr '17, 00:00) arpit7281★

@neilit1992

https://pastebin.com/1jEifb09

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

(09 Apr '17, 00:21) arpit7281★

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?

(09 Apr '17, 00:35) neilit19923★

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

(09 Apr '17, 00:55) vijju123 ♦♦4★

He needs to find greatest factor whose number of factor is of power 2, this what i understood

(09 Apr '17, 01:02) neilit19923★

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

(09 Apr '17, 02:08) vijju123 ♦♦4★

@vijju123

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:30) arpit7281★

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

(09 Apr '17, 07:49) arpit7281★

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

(09 Apr '17, 11:27) neilit19923★

@neilit1992

Can you brief, what exactly you are doing.

(09 Apr '17, 12:00) arpit7281★

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

(09 Apr '17, 12:16) neilit19923★

@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

(09 Apr '17, 13:22) arpit7281★

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

(09 Apr '17, 13:30) neilit19923★
1

@neilit1992

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

(09 Apr '17, 14:47) arpit7281★

@neilit1992

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

(09 Apr '17, 14:53) arpit7281★

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.

(09 Apr '17, 15:24) neilit19923★

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.

(09 Apr '17, 15:51) vijju123 ♦♦4★
1

@vijju123

Thanks a lot, my problem is solved.

(09 Apr '17, 17:01) arpit7281★
showing 5 of 20 show all
#include <iostream>
#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.

link

answered 08 Apr '17, 20:35

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859
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 ♦♦4★

@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) vijju123 ♦♦4★

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)

link

answered 08 Apr '17, 19:42

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859
accept rate: 18%

edited 08 Apr '17, 19:43

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

(08 Apr '17, 20:05) arpit7281★

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

link

answered 10 Apr '17, 10:31

ankurdua15's gravatar image

6★ankurdua15
611
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) neilit19923★

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.

link

answered 09 Apr '17, 01:05

hemanth_1's gravatar image

6★hemanth_1
1.4k11
accept rate: 28%

edited 09 Apr '17, 12:36

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

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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