Prime Factorization

Prime numbers are natural numbers greater than 1 that cannot be formed by multiplying two smaller numbers. For example, 7 is prime since it can only be formed by 1 × 7. Other examples include 2, 3, 5, 11, etc. Numbers that can be formed with two other natural numbers greater than 1 are called composite numbers (e.g., 4, 6, 9).

Prime factorization is the decomposition of a composite number into a product of prime numbers. The fundamental theorem of arithmetic states that natural numbers greater than 1 are either prime, or can be factored as a product of prime numbers.

Trial division: One method involves testing each integer by dividing the composite number by the integer, and determining if the integer can divide the number evenly. This process continues until only 1 remains.

Prime decomposition: Another common way is to use a factor tree, breaking up the composite number into factors until all numbers are prime. For very large numbers, there is no known efficient algorithm.