Efficient Prime Factorization Algorithm (Integer Factorization)


Given an integer n greater than 1, find all of its prime factors and return them in sorted order. You can write out a number as a product of prime numbers, which are its prime factors. The same prime factor may occur more than once. For example, given 12, return [2, 2, 3] since 2 * 2 * 3 = 12.

Example 1
Input
n = 12
Output
[2, 2, 3]
Explanation
2 * 2 * 3 = 12

Integer Factorization Algorithm

The Factorization (Integer or Prime Factorization) process is used to represent any positive integers by a product of prime numbers. For example, 6 = 2×3 and 12 = 2x2x3. The integer factorization is not trivial, but there is an efficient algorithm to do this.

First, we need to find all prime factor 2. We can do this by repeatedly dividing the integer by two if we can. Then we start with prime number 3 and increment each by two (we can skip even numbers as this has been dealt with in the first step).

We can find factors up to square root of N. Once finished, we need to add the updated-n if it is bigger than 2 because it might be a prime number (remaining factor).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> primeFactorization(int n) {
    vector<int> ans;
    while (n % 2 == 0) {
        ans.push_back(2);
        n /= 2;
    }
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            n /= i;
            ans.push_back(i);
        }
    }
    if (n > 2) { // for primes larger than 2
        ans.push_back(n);
    }
    return ans;
}
vector<int> primeFactorization(int n) {
    vector<int> ans;
    while (n % 2 == 0) {
        ans.push_back(2);
        n /= 2;
    }
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            n /= i;
            ans.push_back(i);
        }
    }
    if (n > 2) { // for primes larger than 2
        ans.push_back(n);
    }
    return ans;
}

The algorithm complexity is O(sqrt(n)) and O(M) space where M is the number of the prime factors.

This online tool efficiently implements this algorithm: Integer Factorization to Prime Factors with API

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
378 words
Last Post: Single Core CPU Scheduling Algorithm by Using a Priority Queue
Next Post: Depth First Search and Breadth First Search Algorithm in Checking Sum of Children Nodes in Binary Tree

The Permanent URL is: Efficient Prime Factorization Algorithm (Integer Factorization)

Leave a Reply