Please provide an integer to find its prime factors as well as a factor tree.
What is a prime number?
Prime numbers are natural numbers (positive whole numbers that sometimes include 0 in certain
definitions) that are greater than 1, that cannot be formed by multiplying two smaller numbers. An
example of a prime number is 7, since it can only be formed by multiplying the numbers 1 and 7. Other
examples include 2, 3, 5, 11, etc.
Numbers that can be formed with two other natural numbers, that are greater than 1, are called composite
numbers. Examples of this include numbers like, 4, 6, 9, etc.
Prime numbers are widely used in number theory due to the fundamental theorem of arithmetic. This theorem
states that natural numbers greater than 1 are either prime, or can be factored as a product of prime
numbers. As an example, the number 60 can be factored into a product of prime numbers as follows:
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 factorization is the decomposition of a composite number into a product of prime numbers. There are
many factoring algorithms, some more complicated than others.
Trial division:
One method for finding the prime factors of a composite number is trial division. Trial division is one
of the more basic algorithms, though it is highly tedious. It involves testing each integer by dividing
the composite number in question by the integer, and determining if, and how many times, the integer can
divide the number evenly. As a simple example, below is the prime factorization of 820 using trial
division:
820 ÷ 2 = 410
410 ÷ 2 = 205
Since 205 is no longer divisible by 2, test the next integers. 205 cannot be evenly divided by 3. 4 is
not a prime number. It can however be divided by 5:
205 ÷ 5 = 41
Since 41 is a prime number, this concludes the trial division. Thus:
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 common way to conduct prime factorization is referred to as prime decomposition, and can involve
the use of a factor tree. Creating a factor tree involves breaking up the composite number into factors
of the composite number, until all of the numbers are prime. In the example below, the prime factors are
found by dividing 820 by a prime factor, 2, then continuing to divide the result until all factors are
prime. The example below demonstrates two ways that a factor tree can be created using the number 820:
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.
