Integer Factorization
Introduction
Before jumping into learning about various integer factorization algorithms, let’s quickly revise the prerequisite 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 = p_{1 }x p_{2} x . . . . p_{N}, where p_{1}, p_{2, }and p_{N }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
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 to store 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.
 Perform following operations while N is divisible by 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>

Input
Enter the number: 1521345 
Output
Factors of 1521345 are: 3 5 7 14489 
Wheel Factorization
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 (p_{1}, p_{2},...p_{N} ) ranging between 2 to √N (Say 2, and 3).
 Find the coprimes of the selected primes(p_{1}, p_{2},...p_{N} ) . The coprimes should be less than LCM(p_{1}, p_{2},...p_{N} )
All these selected primes and coprimes 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 coprimes 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 coprimes, 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.
 While N % divisor == 0.
 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>
return factors; 
Input
Enter the number: 546565 
Output
Factors of 546565 are: 5 109313 
Before we move on to the next section, let’s look at some of the scenarios with different primes in selectedPrimes list.
selectedPrimes = {2, 3, 5}
LCM(selectedPrimes) = LCM(2,3, 5) = 30
Coprimes between 0 to 30 = { 7, 11, 13, 17, 19, 23, 29}
selectedPrimes = {2, 3, 5, 7}
LCM(selectedPrimes) = LCM(2,3, 5, 7) = 210
Coprimes between 0 to 210 = { 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, 121, 127,
131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179
181, 187, 191, 193, 197, 199, 209}
You can notice how fast the coprimes 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.
 While N % divisor == 0.
 If N > 1
 Push N to factors.
 Return factors.
Refer to the code given below for a better understanding.
Code
#include <bits/stdc++.h> /* If current is true, if(sieve[i]) primes.push_back(i); of the current element to composite. */
while (N % divisor == 0) { factors.push_back(N); 
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 CodeStudio. Good coders always practice what they learn. CodeStudio 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.
Happy Coding!
Pranav Gautam
Comments
No comments yet
Be the first to share what you think