Here is an example if you want to use the primes number to go a lot faster. These lists are easy to find on the internet. I added comments in the code. # http://primes.utm.edu/lists/small/10000.txt
# First 10000 primes
_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
# Mising a lot of primes for the purpose of the example
)
from bisect import bisect_left as _bisect_left
from math import sqrt as _sqrt
def get_factors(n):
assert isinstance(n, int), "n must be an integer."
assert n > 0, "n must be greather than zero."
limit = pow(_PRIMES[-1], 2)
assert n <= limit, "n is greather then the limit of {0}".format(limit)
result = set((1, n))
root = int(_sqrt(n))
primes = [t for t in get_primes_smaller_than(root + 1) if not n % t]
result.update(primes) # Add all the primes factors less or equal to root square
for t in primes:
result.update(get_factors(n/t)) # Add all the factors associted for the primes by using the same process
return sorted(result)
def get_primes_smaller_than(n):
return _PRIMES[:_bisect_left(_PRIMES, n)]
First, 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 C++ as well as Python January 14, 2017 - 7 minute read - A 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 . Table of Contents - How to find the factors of a number?
- Brute Force Python Implementation to find factors of a number
- Efficient method to find factors of a number
- Efficient Python Implementation to find factors of a number
- Efficient C++ Implementation to find factors of a number
How to find the factors of a number?Let’s find all 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 i - Check if
x % i == 0 , we add it to our list of factors
Brute Force Python Implementation to find factors of a number1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| def 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 result
print 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 result within 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 every 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 24 by looping till 4 . Let’s take another example, 16 : 16 = 1 x 16
16 = 2 x 8
16 = 4 x 4
16 = 8 x 2
16 = 16 x 1
Again, 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 i - If
x % i == 0 , then add i to the list of factors - Now 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 .
- 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 code
Efficient Python Implementation to find factors of a number1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| def 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: # In Python, // operator performs integer/floored division
result.append(x//i)
i += 1
# Return the list of factors of x
return result
print 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]
|
Efficient C++ Implementation to find factors of a number1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <iostream>
#include <vector>
// Switch DEBUG to false if you don't want to print the factors
#define DEBUG true
using namespace std;
vector <int> factors(int x) {
// We will store all factors in `result`
vector <int> result;
int 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.push_back(i);
// Handle the case explained in the 4th
if(x/i != i) {
result.push_back(x/i);
}
}
i++;
}
// Print in case of debug mode
if(DEBUG) {
for(int i=0; i<result.size(); i++) {
cout << result[i] << ' ';
}
cout << endl;
}
// Return the list of factors of x
return result;
}
int main() {
factors(1);
// Output: 1
factors(4);
// Output: 1 4 2
factors(10);
// Output: 1 10 2 5
factors(12);
// Output: 1 12 2 6 3 4
factors(16);
// Output: 1 16 2 8 4
return 0;
}
|
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. Got a burning question you might wanna get answered? Ask it in the comments. Software Engineer, a product person, delves into graphic designs on lazy weekends or writes blog posts about software engineering and life experiences.
Retired competitive programmer.
How do you find factors efficiently?
Best Approach: If you go through number theory, you will find an efficient way to find the number of factors. If we take a number, say in this case 30, then the prime factors of 30 will be 2, 3, 5 with count of each of these being 1 time, so total number of factors of 30 will be (1+1)*(1+1)*(1+1) = 8.
How do you find the factor of a number in Python?
Source Code
Note: To find the factors of another number, change the value of num . In this program, the number whose factor is to be found is stored in num , which is passed to the print_factors() function. This value is assigned to the variable x in print_factors() .
How do you find the factors of a number in coding?
Program to find factors of a number - an efficient approach. #include <stdio.h>. #include <math.h>. int find_factors(int num). for (int i=1; i<=sqrt(num); i++). if (num % i == 0).
|