The fundamental theorem of arithmatic states that any number greater than 1 can be represented as a product of primes and this form of represenation is unique. Remember factoring integers in grade school? That’s exactly what we’re talking about. Now we’ll see two proofs which’ll provide you the intuition why this works.

Every integer n, n \gt 1 is divisible by at least a prime.

If n is a prime, then the lemma is proved since n \mid n. But when n is a composite number, we know there exists a divisor d_1 such that 1 < d_1 < n, then n = d_1n_1. If n_1 is a prime, we’re done. But if it is composite, then n1=d_2n_2 for some n_2 where 1 < n_2 < n_1. If n_2 is a prime, we’re done. But if it is composite, then n_2 = d_3n_3 for some integer n_3 with 1 < n_3 < n_2. Among the numbers n, n_1, n_2, n_3, n_4, … a prime will eventually appear because

n > n_1 > n_2 > n_3 > n_4 > n_5 > …

where each n_i is greater than 1. It is impossible for a decreasing sequence of positive integers to continue forever. The prime that eventually appears, let’s say it n_k which divides n because n_k \mid n_{k-1}, \quad n_{k-1} \mid n_{k-2}, \quad n_{k-2} \mid n_{k-3}, \quad n_1 \mid n implies n_k \mid n.

Every integer n, n > 1 can be expressed as a product of primes.

From lemma 1, we know that n has at least 1 prime divisor. Let p_1 be that divisor, then n = p_1n_1 where 1 \leq n_1 < n. Now if n_1 = 1 we know that n itself is a prime and we are done. But when n_1 > 1, there is a prime that divides n_1. That is n_1=p_2n_2, where p_2 is a prime when 1 \leq n_2 < n_1. Again if n_2 = 1, we are done. We sooner or later come to one of the n_i equal to 1 because n > n_1 > n_2 > … and n_i is positive. Such a sequence can not continue forever.

For some k, we will have n_k = 1, in which case n = p_1 \times p_2 \times p_3 \times . . . \times p_n is the desired expression of n as a product of primes. Note that p_1, p_2 the same prime may occur several times in the product.

### Usage of prime factorization

- If we have two integers a, b and we can find gcd(a, b) from the prime factorization of a, b. Suppose a = 2^{a_1} \times 3^{a_2} \times 5^{a_3}… and b = 2^{b_1} \times 3^{b_2} \times 5^{b_3}…, then we can write a \times b = 2^{a_1 + b_1} \times3^{a_2+b_2} \times5^{a_3 + b_3}…. Now, if we take the min(a_i, b_i) for each p_i we get the common portion for that p_i. In this way, we can keep multiplying the common portions to get gcd(a, b). Thus mathematically if ab = p_1^{a_1 + b_1} \times p_2^{a_2 + b_2} \times p_3^{a_3 + b_3} \times … \times p_n^{a_n + b_n} then,

gcd(a, b) = \prod p_i^{min(a_i , b_i)}

- Simillarly, given two integers a, b we can find lcm(a, b) from the prime factorization of a, b. But This time we have to make min(p_i, b_i) for each p_i. Thus mathematically if ab = p_1^{a_1 + b_1} \times p_2^{a_2 + b_2} \times p_3^{a_3 + b_3} \times … \times p_n^{a_n + b_n} then,

lcm(a, b) = \prod p_i^{max(a_i , b_i)}

- Having the prime factorization of a number, we can easily find the number of divisors of that number. This turns out to be an application of the multiplication principle for counting. Suppose we want to count the number of divisors of n = 144. The facorization of 144 is 2^4 \times 3^2. So any divisor of 144 must be a product of some number of 2’s (between 0 and 4) and some number of 3’s (between 0 and 2).

2^0 2^1 2^2 2^3 2^4 3^0 1 2 4 8 16 3^1 3 6 12 24 48 3^2 9 18 36 72 144 From the table, it’s easy to see that there are 5 \times 3 = 15 divisors of 144. We can generalize that, if we have a integer where n = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} … \times p_j^{a_j} then,

NOD(n) = \prod \limits_{i=1} \limits^{j} (a_i + 1)

- Having the prime factorization of a number, we can also find the sum of divisors of that number. Consider a number that is a power of a prime n = 2^3 = 8. The divisors of n are 1, 2, 4, 8 that is, 2^0, 2^1, 2^2, and 2^3. The sum of these forms a geometric series, so we can use the formula \frac{2^4 – 1}{2 – 1} = 15. Now consider a number formed by multiplying powers of two primes, any divisor of n = 2^3 \times 3^2 = 72. We can get the sum of divisors from the following expression (2^0 + 2^1 + 2^2 + 2^3) \times (3^0 + 3^1 + 3^2). In order to understand if you expand and evaluate the expression, you’ll get 1 + 2 + 4 + 8 + 3 + 6 + 12 + 24 + 9 + 18 + 36 + 72 = 195. To generalize this, if we have a integer where n = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} … \times p_j^{a_j} then,

SOD(n) = \prod \limits_{i = 1} \limits^{j} \frac{p_i^{a_i + 1} – 1}{p_i – 1}

### Computing prime factorization

One way to implement the algorithm is to keep dividing by a_i in the range a = [2, \sqrt{n}] while a_i | n and push a_i in our resulant vector. After the process, If the n > 1 then n should be also included into the resulant vector. The reason we go only upto \sqrt{n} is because a composite has at most 1 prime divisor greater than \sqrt{n}. All other primes numbers are less than or equal to \sqrt{n}. So, we can only go upto \sqrt{n} and if something is left after the process, that is the prime greater than \sqrt{n}.

```
void factorize(int n, vector<int> &res) {
for (int i = 2; i * i <= n; ++i) {
while (n % i == 0) {
res.push_back(i);
n /= i;
}
}
if (n > 1)
res.push_back(n);
}
```

The time complexity of this algorithm is O(\sqrt{n}). But we can do better. How? Notice that we are doing the prime factorization, but in the loop we are iterating in the range [2, \sqrt{n}]. In that range, there are many composite numbers and if you think carefully you’ll see that a composite number will never divide n, even if that composite number is a divisor of n since n is reduced to some other number by previous prime numbers that came before that composite number. That means in the previous algorithm when i is composite, the while loop will never be true, but the outer for loop will visit all the composite numbers in the range [2, \sqrt{n}]. That’s the unnecessary work that we are doing. We don’t need to visit any composite number. This time we are going to follow the exact process but only with the primes in the range [2, \sqrt{n}].

```
// "p" is an array or vector consisting of
// prime numbers less than or equal to sqrt(n)
// which has to be precomputed by sieve of eratosthenes
vector<int> res;
void factorize(int n) {
for (int i = 0; p[i] * p[i] <= n; ++i) {
while (n % p[i] == 0) {
res.push_back(p[i]);
n /= p[i];
}
}
if (n > 1)
res.push_back(n);
}
```

## No Comments

Leave a comment Cancel