Please provide an integer to find its prime factors as well as a factor tree.
What is a prime number?
Prime numbers are positive integers greater than 1 that cannot be expressed as a product of two smaller natural numbers. For instance, 7 is prime because its only divisors are 1 and 7. Other small primes are 2, 3, 5, 11 and so on.
Numbers that can be written as the product of two natural numbers exceeding 1 are called composite numbers. Typical examples are 4, 6, 9, etc.
In number theory the fundamental theorem of arithmetic tells us that every integer above 1 is either a prime itself or can be broken down into a multiplication of prime factors. Take 60, which can be expressed as 2 × 2 × 3 × 5.
60 = 5 × 3 × 2 × 2
As can be seen from the example above, there are no composite numbers in the factorization.
What is prime factorization?
Prime factorisation means splitting a composite integer into a set of prime numbers whose product equals the original number. Various algorithms exist for this task, ranging from simple to highly sophisticated.
Trial division:
A straightforward way to obtain the prime factors of a composite number is the trial‑division method. It repeatedly tests whether the number can be divided without remainder by successive integers, counting how many times each divisor fits. As an illustration, the factorisation of 820 by trial division is shown below.
820 ÷ 2 = 410
410 ÷ 2 = 205
After eliminating the factor 2, 205 is no longer even, so we move to the next candidates. It is not divisible by 3, and 4 is not prime, but 5 divides it exactly.
205 ÷ 5 = 41
Since 41 itself is prime, the trial‑division process stops here, giving the final decomposition as follows:
820 = 41 × 5 × 2 × 2
The products can also be written as:
820 = 41 × 5 × 22
This is essentially the "brute force" method for determining the prime factors of a number, and though 820 is a simple example, it can get far more tedious very quickly.
Prime decomposition:
Another popular technique for prime factorisation is called prime decomposition, often visualised with a factor tree. This approach repeatedly breaks a composite number into two factors until all resulting branches are prime. Using 820 as an example, a factor tree can be built in at least two distinct ways, each ultimately revealing the same set of prime factors.
820
/ \
410 2
/ \
205 2
/ \
41 5
820
/ \
205 4
/ \ / \
41 5 2 2
Thus, it can be seen that the prime factorization of 820, in either case, again is:
820 = 41 × 5 × 2 × 2
While these methods work for smaller numbers (and there are many other algorithms), there is no known algorithm for much larger numbers, and it can take a long period of time for even machines to compute the prime factorizations of larger numbers; in 2009, scientists concluded a project using hundreds of machines to factor the 232-digit number, RSA-768, and it took two years.
Prime factorization of common numbers
The following are the prime factorizations of some common numbers.