04.15.2022 - Math/Prime Factorization Uniqueness
In mathematics, the fundamental theorem of arithmetic◹ states that: “Any integer number larger than 1 can be written as a product of prime numbers in one and only one way”.
No matter how you come up with the prime factorization, the set of prime factors might have a different order, but they are always the same set.
In algorithm problem solving, the uniqueness of a prime factorization can be applied in some situations, for example, to check if two strings are made up from the same set of characters, with a different arrangement (anagram).
The idea to solve this kind of problem is, to map the characters in each string to a prime number:
Then multiply them together, if they made up the same integer number, then they’re anagram.
Suppose we have an integer $n$ that has two distinct prime factorizations $n = p_1 \times p_2 \times p_3 \times \cdots \times p_j$ and $n = q_1 \times q_2 \times q_3 \times \cdots \times q_k$, where each $p_i$ and $q_i$ is a prime.
We see that $p_1$ divides $n$, so $p_1$ divides $q_1 \times q_2 \times q_3 \times \cdots \times q_k$. By Euclid’s lemma◹, we have that $p_1$ divides some $q_i$, let’s say $q_1$.
Since $p_1$ and $q_1$ are both prime, they must be the same, so $p_1 = q_1$. Cancel both $p_1$ and $q_1$ from the two prime factorizations, we get:
p_2 \times p_3 \times \cdots \times p_j = q_2 \times q_3 \times \cdots \times q_k
Continue the process, eventually, we will find that each $p$ is a $q$. After each cancellation, we cannot run out of $p$ before all the $q$ are gone. This means, $p_1 \times p_2 \times p_3 \times \cdots \times p_j$ are just a rearrangement of $q_1 \times q_2 \times q_3 \times \cdots \times q_k$. The two factorizations are just differ in the order of the factors.
- 04.18.2022 - Algorithms/Detect chess piece movement with Bitboard
- 04.17.2022 - Data Structures/Introduction to Bitboard
- 04.16.2022 - Math/Circle and Ray Intersection
- 04.14.2022 - TypeScript/Understanding “keyof typeof”
- 04.13.2022 - Reading Notes/Detect Infinite Recursive Call with Control Flow Graph