Before jumping into learning about various integer factorization algorithms, let’s quickly revise the pre-requisite knowledge. All numbers can be divided into two categories based on the number of factors:
Prime number: Numbers having only two factors (1 and itself).
Composite number: Numbers that are not prime.
Integer factorization refers to finding the prime factors of a number. For prime numbers, it is easy as a prime number has only two factors, one and itself.
For a composite number N, list all the prime numbers that divide N with a remainder 0. A composite number has at least two prime factors. So, N is represented as N = p1 x p2 x . . . . pN, where p1, p2, and pN are the prime factors.
Note: At least one of the prime factors of a composite number is less than or equal to √N.
Now that you know about the required concepts let’s dive right into learning integer factorization algorithms.
Trial division is a brute force method. Remember, the prime factors of a composite number are present from 2 to √N.If no such divisor is present in the range [2, √n], then N must be a prime number. So, the simplest way to perform integer factorization is by iterating through the list 2 to √N and adding all the prime factors that divide N completely in our answer.
Algorithm
Create a vector, factors tostore the factors of the number N.
Loop an integer divisor through 2 to √N.
Perform following operations while N is divisible by divisor.
Insert divisor in factors.
Divide N by the divisor.
If N is greater than 1.
Insert N in factors.
Return factors.
Refer to the program given below for a better understanding of the algorithm.
Program
#include <bits/stdc++.h> usingnamespacestd;
vector<int> trialDivision(int N) {
// Vector to store the prime factors. vector<int> factors;
// Iteration from 2 to √N. for(int divisor = 2; divisor * divisor <= N; divisor++){ while(N % divisor == 0) { factors.push_back(divisor); N /= divisor; } }
The trial division method checks the divisibility of the number N with numbers ranging from 2 to √N. The list of numbers from 2 to √N may contain prime and composite numbers. As composite numbers are multiplications of two or prime numbers, there is no point in checking the divisibility of N with a composite number.
The wheel factorization method helps in removing some of these composite numbers to find the prime factors. How is it done? Follow the procedure given below:
Consider some prime numbers (p1, p2,...pN ) ranging between 2 to √N (Say 2, and 3).
Find the co-primes of the selected primes(p1, p2,...pN ) . The co-primes should be less than LCM(p1, p2,...pN )
All these selected primes and co-primes create the list of prime numbers for integer factorization.
Let’s say the selected prime list has only two primes: 2 and 3. Once the primes are selected, we need to find the list of co-primes in batches of size LCM(selected primes). So, for this example, the LCM(2, 3) = 6. Thus, the numbers will be divided in batches of 6 numbers such as 1 to 6, 7 to 12 etc. Refer to the table given below:
Column 1
Column 2
Column 3
Column 4
Column 5
Column 6
1
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
Initially, the integer factorization had to be done for all the numbers ranging from 2 to √N. As columns 2, 3, 4, and 6 have multiples of the selected primes and co-primes, these columns can be skipped. Now, we need to check the elements from columns 1 and 5 for integer factorization.
Our checklist comes down from 6 columns to only 2 columns. The reduction percentage of columns can be calculated as (Columns to be checked * 100) / Total number of columns. Thus, for 2 selected primes, the reduction is 33.33%. The more primes we choose, the more columns are skipped.
Have you noticed that the number 25 is a composite number and is present in column 1? 25 is not included in the answer because its prime factor is already pushed to the solution. Wheel factorization is not an excellent method to generate prime factors. But, It is a fast method to check whether the given number is a prime or composite number. Also, it helps in avoiding composite numbers. But, the bigger your selected primes list gets, the more composite numbers tend to include in the checklist.
Algorithm
Create a vector, factors to store the factors of N.
Iterate through the selectedPrimes list using iterator: divisor.
While N % divisor == 0.
Push divisor to factors.
Divide N by divisor.
Create a checklist vector coprimes.
Iterate i from 0 to √N with an increment of LCM(selectedPrimes).
Iterate through coprimes with iterator currentCoPrime.
Set divisor = i + currentCoPrime.
If divisor > √N.
continue.
While N is divisible by divisor.
Push divisor to factors.
Divide N by divisor.
If N > 1
Push N to factors.
Return factors.
Program
#include <bits/stdc++.h> usingnamespacestd;
vector<int> wheelFactorization(int N) {
vector<int> factors;
// Integer factorization for selected primes. vector<int> selectedPrimes = {2, 3}; for(auto prime : selectedPrimes) { while(N % prime == 0) { factors.push_back(prime); N /= prime; } }
// Integer factorization for selected co-primes in the checklist. vector<int> coPrimes = {1, 5}; for(int i = 0; i*i <= N; i += 6) {
You can notice how fast the co-primes list gets more significant with each additional prime in the selectedPrimes list.
Precomputed Primes
The wheel factorization method is a great improvement for integer factorization. But, can we do better? Yes, we can. Wheel factorization helps us to remove some of the composite numbers from the 2 to √N list. If all the composite numbers are removed from the list, the integer factorization can be more efficient. Sieve of Eratosthenes can be used to create an array of prime numbers. The primes stored in the sieve can be used to perform integer factorization.
Algorithm
Create a vector primes to store prime numbers.
Fill primes with prime numbers ranging from 2 to √N using Sieve of Eratosthenes.
Create vector factors to store the factors.
Iterate through the primes using iterator: divisor.
While N % divisor == 0.
Push divisor to factors.
Divide N by divisor.
If N > 1
Push N to factors.
Return factors.
Refer to the code given below for a better understanding.
Code
#include <bits/stdc++.h> usingnamespacestd;
// Helper function. voidsieveOfEratosthenes(vector<int> &primes, int N){
/* Creating a boolean sieve of size sqrt(N). Elements with true value will be considered prime. Elements with false values will be considered composite. */ vector<bool> sieve(N + 1, true);
for(int i = 2; i <= N ; i++) {
/* If current is true, no element before current is a factor of current element. */
if(sieve[i])
primes.push_back(i);
/* Changing all the multiplications(upto sqrt(N))
of the current element to composite. */ for(int j = 2; i * j <= N; j++) { sieve[i * j] = false; }
}
return; }
vector<int> precomputedPrimes(int N) {
vector<int> primes;
// Filling primes array using sieveOfEratosthenes. sieveOfEratosthenes(primes, sqrt(N));
// Integer factorization of N using precomputedPrimes. vector<int> factors; for (auto divisor : primes) {
while (N % divisor == 0) { factors.push_back(divisor); N /= divisor; } }
if(N > 1)
factors.push_back(N); return factors; }
// Driver Function. intmain() {
int N; cout << "Enter the number: "; cin >> N;
vector<int> factors = precomputedPrimes(N);
cout << "\nFactors of " << N << " are: "; for(int factor : factors) cout << factor <<" ";
return0; }
Input
Enter the number: 37
Output
Factors of 37 are: 37
You might have noticed that the sieveOfEratosthenes() function is invoked every time for integer factorization of every new number. A significant optimization can be to fill the primes once using sieveOfEratosthenes() outside of the helper function. This will save time by not calling sieveOfEratosthenes() for every integer factorization. However, huge space is required to store that many prime numbers.
Key Takeaways
Every number is unique, and so are you. Keep learning to make yourself as one of a kind as prime numbers are. Integer factorization is just the beginning.
You can learn many such interesting concepts from Coding Ninjas Studio. Good coders always practice what they learn. Coding Ninjas Studio offers top problems to make your practice experience more friendly. Don’t know where to start from? Check out our guided paths, and you’ll find your way.
38+ registered 