Integer Factorization

Pranav Gautam
Last Updated: May 13, 2022

Introduction

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 with a remainder 0. A composite number has at least two prime factors. So, is represented as N = px p2 x . . . . pN, where p1, p2, and pare 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 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 is divisible by divisor.
      • Insert divisor in factors.
      • Divide by the divisor
  • If is greater than 1.
    • Insert in factors.
  • Return factors.

 

Refer to the program given below for a better understanding of the algorithm.

Program

#include <bits/stdc++.h>
using namespace std;

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;
   }
  }

  if(N > 1) {
factors.push_back(N);
      }

  return factors;
}


// Driver Function.
int main() {

      int N;
      cout << "Enter the number: ";
  cin >> N;

  vector<int> factors = trialDivision(N);

cout << "\nFactors of " << N << " are: ";
  for(int factor : factors) {
  cout << factor <<" ";
      }
      
      return 0;
}

 

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

  1. Consider some prime numbers (p1, p2,...pN ) ranging between 2 to √N (Say 2, and 3). 
  2. 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 divisor == 0.
      • Push divisor to factors.
      • Divide 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 icurrentCoPrime.
    • If divisor √N. 
      • continue.
    • While N is divisible by divisor.
      • Push divisor to factors.
      • Divide by divisor. 
  • If > 1
    • Push N to factors.
  • Return factors.

Program

#include <bits/stdc++.h>
using namespace std;

vector<int> wheelFactorization(int N) {

      vector<int> factors;

      // Integer factorization for selected primes.
  vector<int> selectedPrimes = {23};
  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 = {15};
  for(int i = 0; i*i <= N; i += 6) {


   for(int currentCoPrime : coPrimes) {
     int divisor = i + currentCoPrime;
     if(divisor == 1 || divisor * divisor > N)
       continue;
    
     while(N % divisor == 0) {
       factors.push_back(divisor);
       N /= divisor;
     }


   }
  }

  if(N > 1) {
            factors.push_back(N);
  }

 

      return factors;

}

// Driver Function.
int main() {

      int N;
      cout << "Enter the number: ";
  cin >> N;
 
      vector<int> factors = wheelFactorization(N);
  
   cout << "\nFactors of " << N << " are: ";
  for(int factor : factors)
   cout << factor <<" ";

}

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 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 divisor == 0.
      • Push divisor to factors.
      • Divide by divisor.
  • If N > 1
    • Push to factors.
  • Return factors.

Refer to the code given below for a better understanding.

Code

#include <bits/stdc++.h>
using namespace std;

// Helper function.
void sieveOfEratosthenes(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 + 1true);

  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.
int main() {

      int N;
     cout << "Enter the number: ";
  cin >> N;

     vector<int> factors = precomputedPrimes(N);

     cout << "\nFactors of " << N << " are: ";
  for(int factor : factors)
     cout << factor <<" ";

return 0;
}

 

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

 

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think