Efficient way to find factors of a number — Python CodeDiogo RibeiroBlockedUnblockFollowFollowingApr 30First, we will see how to find all factors of a number using brute force.
Then we will improve upon that to find all factors of a number using the most efficient method and code it in PythonA factor of a number x is a number y if y divides x without leaving a remainder.
That is if x % y == 0 we say that y is a factor of x.
How to find the factors of a number?Let’s find all the factors of 24.
We know all the factors of 24 are 1, 2, 3, 4, 6, 8, 12, 24.
How can we find them programmatically?Common factors are 1, 2, 3, and 6.
Since 6 is the highest of them, GCD of 24 and 18 is 6.
The breakdown of the process of finding factors of a number x is:Iterate from 1 to x, call that number iCheck if x % i == 0, we add it to our list of factorsBrute Force Python Implementation to find factors of a numberdef factors(x): # We will store all factors in `result` result = [] # This will loop from 1 to x for i in xrange(1, x+1): # Check if i divides x without leaving a remainder if x % i == 0: result.
append(i) # Return the list of factors of x return resultprint factors(1)# Output: [1]print factors(4)# Output: [1, 2, 4]print factors(10)# Output: [1, 2, 5, 10]print factors(12)# Output: [1, 2, 3, 4, 6, 12]print factors(16)# Output: [1, 2, 4, 8, 16]Time Complexity of the above algorithm is O(N), N being the number for which we want to find all factors.
If we were to find factors of a number as large as billion i.
e.
of the order of 1000000000, above code will not produce a result within a reasonable time.
Go ahead, try it out!How can improve upon that?.We notice that the factor of any number x is always less than x/2.
So instead of looping up to x, we can loop up to x/2.
This will bring down the time to half but it is still not very efficient.
Also, O(N/2) boils down to O(N).
Efficient method to find factors of a numberIf we analyze the factors of 24, they are 1, 2, 3, 4, 6, 8, 12, 24.
We notice that, 1 x 24 = 24, so when we found that 1 is a factor of 24, we also know that 24 is yet another factor.
Similarly, 2 x 12 = 24.
So when we found that 2 is a factor of 24, we also know that 12 is also a factor of 24.
This applies for 3 x 8 and 4 x 6 as well.
This means that we can find all factors of 24by looping till 4.
Let’s take another example, 16:16 = 1 x 1616 = 2 x 816 = 4 x 416 = 8 x 216 = 16 x 1Again, we can loop till 4 and find all the factors of 16.
In this way, in order to find factors of x, we have to loop till sqrt(x).
Process of finding all factors of x in efficient way;Loop from 1 to sqrt(x), call it iIf x % i == 0, then add i to the list of factorsNow if x % i == 0, we can say for sure that, x/i is also a factor of x.
So, add x/i to the list of factors.
For example: in case of 16, we see that 16 % 2 == 0, now 16/2 which is 8 is also a factor of 16.
4.
There is one catch in the above step.
What if i is same as x/i?For example: in case of 16, when i = 4, 16 % 4 == 0, so we add i and 16/i to list of factors, but 16/i is also 4.
We will have to handle this case while converting the process into codeEfficient Python Implementation to find factors of a numberdef factors(x): # We will store all factors in `result` result = [] i = 1 # This will loop from 1 to int(sqrt(x)) while i*i <= x: # Check if i divides x without leaving a remainder if x % i == 0: result.
append(i) # Handle the case explained in the 4th if x/i != i: result.
append(x/i) i += 1 # Return the list of factors of x return resultprint factors(1)# Output: [1]print factors(4)# Output: [1, 4, 2]print factors(10)# Output: [1, 10, 2, 5]print factors(12)# Output: [1, 12, 2, 6, 3, 4]print factors(16)# Output: [1, 16, 2, 8, 4]Time Complexity of the above algorithm to find factors is O(sqrt(N)).
Go ahead, try to find factors of a number as large as 1000000000, this implementation will return the result in flash.
.