Prime Factors

Authors: @Ishwarendra @wingkwong

Overview

A prime factor is a factor of a number that is also a prime number. For example, the prime factors of $12$ are $2$ and $3$, as $12 = 2 * 2 * 3$. Prime factorization is the process of finding the prime factors of a number. This can be done by repeatedly dividing the number by prime numbers until the remaining number is also a prime number. The prime factorization of a number is unique, meaning that there is only one combination of prime numbers that multiply together to equal that number. The prime factorization of a number can be useful in solving mathematical problems such as finding the greatest common divisor (GCD) of two numbers or the least common multiple (LCM) of two numbers.

Approach #1: Finding prime factor in $\sqrt n$ time

We know that every composite number $N$ has a prime factor less than $N$. Thus, we can iterate over numbers from $2$ to $N$ and whenever we find number that divides $N$ we divide $N$ by it until it no longer divides $N$.

But wouldn't we accidently divide N by a non-prime number this way?

No, we won't because every composite number has a prime factor less than $N$ so as we iterate over $2$ to $N$ we will cancel out all prime factors of any non-prime numbers from $N$ making it indivisible by that non-prime number.

We can further speed up our algorithm by using the fact that a number can have atmost $1$ prime factor greater than $\sqrt(n)$. This can be easily proved by assuming that a number contains two prime factors greater than $\sqrt{n}$, let's call them $P$ and $Q$.

Since $P > \sqrt n$ and $Q > \sqrt n$ $\implies$ $P \cdot Q > \sqrt n \cdot \sqrt n (= n^2)$. This is not possible as $P$ and $Q$ are prime factor of $N$ so their product must be less than or equal to $N$.

Implementation

C++

Written by @Ishwarendra

vector<int> getPrimeFactors(int n) {
  vector<int> prime_factors;
  // i * i <= n or i <= sqrt(n) both work.
  for (int i = 2; i * i <= n; i++) { 
    while (n % i == 0) {
      prime_factors.emplace_back(i);
      n /= i;
    }
  }
  if (n > 1) prime_factors.emplace_back(n);
  return prime_factors;
}

• Time Complexity: $O(\sqrt{n})$

Approach #2: Finding prime factor in log(n) time

Before moving further, it's important to recognise that a number $N$ cannot have more than $log(N)$ prime factors. Since the smallest prime factor a number can have is $2$ and $2^{log(n)} \geq n$. If the number has a prime factor bigger than $2$ than it will have even lesser prime factors. The pre-requisite for this method is knowing Sieve of Eratosthenes.

We can optimise our code to find prime factors of a number $N$ in $O(log(N))$ time. But to do so, we need to do some pre-computations which takes $O(MAX)$ time, where $MAX$ is the largest number upto which we can find it's prime factors. Thus the final time complexity is $O(MAX + log(N))$. This is helpful only if we have to find prime factor of multiple numbers less than or equal to $MAX$.

Since the pre computation takes $O(MAX)$ time so we cannot find prime factors of very large numbers (due to constraints on time) using this method. The pre computation process is a modification of Sieve of Eratosthenes. For each number from $2$ to $MAX$ we find it's smallest prime factor and store it in an array, let's call it min_prime. We will see how to find min_prime array later, first let us see how to calculate prime factor of a number $N$ if we already have the min_prime array in hand.

Implementation

C++

Written by @Ishwarendra

// For sake of simplicity let us assume min_prime is a global vector.
vector<int> getPrimeFactorsInLogn(int n) {
  vector<int> prime_factors;
  while (n > 1) {
    int smallest_prime_factor_of_n = min_prime[n];
    prime_factors.push_back(smallest_prime_factor_of_n);
    n /= smallest_prime_factor_of_n;
  }
  return prime_factors;
}

• Time Complexity: $O(log(n))$, since each time the number $n$ is divided by a number greater than equal to $2$, so it will take only $log(n)$ operation for $n$ to reach $1$.

How to find min_prime array?

vector<int> minPrime(int MAX) {
  vector<int> min_prime(MAX + 1);
  // Set min_prime[i] = i
  iota(begin(min_prime), end(min_prime), 0);
  for (int i = 2; i * i <= MAX; i++) { 
      if (min_prime[i] != i) continue;
      // if min_prime[i] = i then i must be a prime number.
      // Any multiple of i less than i * i (i.e., i * 2, i * 3, ... i * (i - 1)) has a smaller prime factor than i.
      // Any number >= i * i may have i as it's minimum prime factor
      for (int j = i * i; j <= MAX; j += i) min_prime[j] = min(min_prime[j], i);
  }
  return min_prime;
}

Now, that we are aware the techniques used to find prime factors let us solve some problem to get a better grip over the topic.

Example #1: 2521. Distinct Prime Factors Product of Array

Let us take two numbers $A = {p_1} ^ {a_1} \times {p_2} ^ {a_2} \times \cdots \times {p_k} ^ {a_k}$ and $B= {p_1} ^ {b_1} \times {p_2} ^ {b_2} \times \cdots \times {p_k} ^ {b_k}$, where $p_i$ is a prime numbers and $a_i, b_i \geq 0$.

What is $A \times B$?

We know $a^b \times a^c = a^{b + c}$. Using this property we can say that $A \times B = ({p_1}^{a_1 + b_1}) \times ({p_2} ^ {a_2 + b_2}) \times \cdots \times ({p_k}^{a_k + b_k}).$ Thus, we can find prime factor of individual numbers and just add up the power of primes. Function getPrimeFactors(n) is same as coded in the start. To get distinct elements we use set to store all prime factors of all numbers.

C++

Written by @Ishwarendra

int distinctPrimeFactors(vector<int>& nums) {
  set<int> distinct_pf;
  for (auto num : nums) {
    auto pf = getPrimeFactors(num);
    for (auto prime : pf) distinct_pf.emplace(prime);
  }
  return distinct_pf.size();
}

• Time Complexity: $O(n \cdot \sqrt MAX)$, where $MAX$ is the max number present in nums and $n$ is length of nums.
• Space Complexity: O(\text\{number of prime from 2 to MAX}).

We can code same approach using getPrimeFactorsInLogn() function (Method-2).

C++

Written by @Ishwarendra

class Solution {
  vector<int> minPrime(int MAX) {
    vector<int> min_prime(MAX + 1);
    iota(begin(min_prime), end(min_prime), 0);
    for (int i = 2; i * i <= MAX; i++) { 
        if (min_prime[i] != i) continue;
        for (int j = i * i; j <= MAX; j += i) min_prime[j] = min(min_prime[j], i);
    }
    return min_prime;
  }

  // We need to pass the min_prime vector to use inside the function.
  vector<int> getPrimeFactorsInLogn(int n, vector<int> &min_prime) {
    vector<int> prime_factors;
    while (n > 1) {
      int smallest_prime_factor_of_n = min_prime[n];
      prime_factors.push_back(smallest_prime_factor_of_n);
      n /= smallest_prime_factor_of_n;
    } 
    return prime_factors;
  }

public:
  int distinctPrimeFactors(vector<int>& nums) {
    set<int> distinct_pf;
    // Finding the limit upto which we should run sieve.
    const int max = *max_element(begin(nums), end(nums));
    auto min_prime = minPrime(max + 1);
    for (auto num : nums) {
      // Get prime factors of each number in log(n) time.
      auto pf = getPrimeFactorsInLogn(num, min_prime);
      for (auto prime : pf) distinct_pf.emplace(prime);
    }
    return distinct_pf.size();
  }
};

• Time Complexity: $O(MAX + n \cdot log(MAX))$, where $MAX$ is the max element of nums and $n$ is the length of nums.
• Space Complexity: $O(MAX)$, since we need the min_prime vector. Other vector are of size $log(MAX)$ only.

Example #2: 2507. Smallest Value After Replacing with Sum of Prime Factors

In this problem, we have keep replacing $n$ with sum of it's prime factors. We need to stop the process once $n$ becomes prime as a prime number has only two factors $1$ and itself. Since $1$ is not a prime number so it doesn't change. Once our process stops, we will have the minimum number, because sum of prime factor of any number is always less than itself.

Sum of prime factor of any number is always less than or equal to itself. Why?

If we take a composite number then it can be written as product of atleast $2$ different numbers. Let $N$ be a composite number such that $N = A \cdot B$, where $A, B > 1$.

We know that

$$\begin{equation} A \cdot B \geq 2 \cdot A \end{equation}$$$$\begin{equation} A \cdot B \geq 2 \cdot B \end{equation}$$

Adding $(1)$ and $(2)$ we get, $2 \cdot (A \cdot B) \geq 2 \cdot (A + B) \implies A \cdot B \geq A + B.$

C++

Written by @Ishwarendra

class Solution {
public:
  vector<int> getPrimeFactors(int n) {
    vector<int> prime_factors;
    // i * i <= n or i <= sqrt(n) both work.
    for (int i = 2; i * i <= n; i++) { 
      while (n % i == 0) {
        prime_factors.emplace_back(i);
        n /= i;
      }
    }
    if (n > 1) prime_factors.emplace_back(n);
    return prime_factors;
  }

  int smallestValue(int n) {
    while (true) {
      auto pf = getPrimeFactors(n);
      int sum = accumulate(begin(pf), end(pf), 0);
      if (sum == n) break;
      n = sum;
    }
    return n;
  }
};

• Time Complexity: $O(n \cdot sqrt{n} \cdot log(n)$.
• Space Complexity: $O(log(n))$, since there cannot be more than $log(n)$ prime factor of a number $n$.

The above code is bound to come out of while loop in atmost $log(n)$ steps. In the worst case, $n = 2 \cdot P$ where $P = \frac{n}{2}$ is a prime number. In this case $n$ decrease from $n$ to $\frac{n}{2} + 2$ which is approximately $\frac{n}{2}$. Thus at each step $n$ decrease by a factor of $2$. If it has bigger prime factors then it will take even less steps to terminate the while loop.

Example #3: 952. Largest Component Size by Common Factor

This problem requires basic knowledge of graph traversal. The two popular traversals are Depth First Search and Breadth First Search.

First let us see how to build the graph. Naive way of building graph would be to iterate over all $(i, j)$ pairs and check if $\gcd(nums_i, nums_j) > 1$. If it is then add an edge bweten them, else not. But this approch will take $O(n^2)$ operations in worst case, which will not pass.

A different way to build graph could be to add edge between $p$ and $nums_i$ if $p$ is a prime factor of $nums_i$. Since any number $n$ has atmost $log(n)$ prime factors so we will have atmost $n \cdot log(n)$ edges in the graph. But while counting component we need to make sure that the node is present in nums. If it isn't then it can serve as a bridge connecting two numbers from nums, but it should not included in count of nodes in connected component.

An Example

For Example: nums = [6, 8]. In this case $2$ which is a prime factor of $6$ and $8$ acts as a bridge connecting $6$ to $8$ but total connected component should be $2$ only.

Graph for above example looks as shown below. Although total node in the connected component is $4$ but we do not count $2$ and $3$ when reporting answer as it isn't present in nums. Image generated using CS Academy Graph Editor.

Now, as the graph is built we need three main functions:

1. getPrimeFactorsInLogn(n): Gives us prime factor of a number $n$. Since $\max(nums)$ is only $10^5$ so we prefer this function over the one which does the same thing in $\sqrt n$ time.
2. getComponentCount(src): Starting from node $\text{src}$ how many nodes (that are present in nums) can be reached from it.
3. largestComponentSize(nums): The main function that builds graph and use other $2$ functions.

C++

Written by @Ishwarendra

class Solution {
  // isPresent[i] = 1 if i is present in nums, else 0
  // g = graph using which we can find maximum connected component size
  vector<int> isPresent; 
  vector<vector<int>> g;
  vector<int> minPrime(int MAX) {
    vector<int> min_prime(MAX + 1);
    iota(begin(min_prime), end(min_prime), 0);
    for (int i = 2; i * i <= MAX; i++) { 
        if (min_prime[i] != i) continue;
        for (int j = i * i; j <= MAX; j += i) min_prime[j] = min(min_prime[j], i);
    }
    return min_prime;
  }

  vector<int> getPrimeFactorsInLogn(int n, vector<int> &min_prime) {
    vector<int> prime_factors;
    while (n > 1) {
      int smallest_prime_factor_of_n = min_prime[n];
      // Since we only need unique prime factors so we won't push same number again and again
      if (n % smallest_prime_factor_of_n == 0) prime_factors.push_back(smallest_prime_factor_of_n);
      // Remove the prime factor completely from n
      while (n % smallest_prime_factor_of_n == 0) n /= smallest_prime_factor_of_n;
    } 
    return prime_factors;
  }

  int getComponentSize(int src, vector<bool> &vis) {
    queue<int> q;
    q.emplace(src);
    vis[src] = true;
    int count = isPresent[src];
    while (!q.empty()) {
      int node = q.front();
      q.pop();
      for (int child : g[node]) {
        if (!vis[child]) {
          q.emplace(child);
          vis[child] = true;
          // Increase component size only if the number is present in nums.
          count += isPresent[child];
        }
      }
    }
    return count;
  }  
public:
  int largestComponentSize(vector<int>& nums) {
    int max_elem = *max_element(begin(nums), end(nums));
    auto min_prime = minPrime(max_elem + 1);
    isPresent.resize(max_elem + 1);
    g.resize(max_elem + 1);
    vector<bool> vis(max_elem + 1);
    for (int num : nums) {
      isPresent[num] = 1;
      auto pf = getPrimeFactorsInLogn(num, min_prime);
      for (auto prime : pf) {
        if (prime == num) continue;
        // num and prime has gcd > 1
        g[prime].emplace_back(num);
        g[num].emplace_back(prime);
      }
    } 
    int ans = isPresent[1];
    for (int src = 2; src <= max_elem; src++) {
      ans = max(ans, getComponentSize(src, vis));
    }
    return ans;
  }
};

• Time Complexity: $O(MAX + n \cdot log(n))$, where $MAX$ is the max element of nums and $n$ is length of nums.
• Space Complexity: $O(MAX + n \cdot log(n))$, as we are building a graph of $n \cdot log(n)$ edges and $(MAX + 1)$ nodes.

The process of finding connected components can be done using a data structure Disjoint Set Union as well.

Suggested Problems

Problem Name	Difficulty	Solution Link
263. Ugly Number	Easy	View Solutions
650. 2 Keys Keyboard	Medium	View Solutions
2709. Greatest Common Divisor Traversal	Hard	View Solutions