Prime factorization is a method of reducing a number into its prime factors.
Prime factorization is made up of two words prime and factorization, in which prime implies all the prime numbers and factorization implies all the factors.
Hence, by combining these two words, we get prime factorization as the equivalent for getting prime factors of a number.

## Prime Factorization Definition

Prime factors are those numbers which are the basis for further arithmetic study. Any number in the field of mathematics can either be prime or composite but not both.
The method of reducing any given number into the product of its prime is known as the method of factoring.
It is very interesting to note that any composite number can also be reduced into prime factors.
We will now define the concept of prime factorization in detail by defining the following terms:
Definition of Prime Numbers: A prime number is any whole number greater than 1, which can be divided only by two numbers which are:
1).    The number itself and
2).    The number 1.
Prime numbers starts from 2, 3, 5, 7, 11, 13, 17 and so on. Note that the smallest prime number is 2 which is an even number and rest all of the prime numbers are all odd numbers.

Definition of Factors of a Number: Factors are those numbers which when multiplied by each other give us another number, as can be seen from the following numbers which are factors of 6:

Note that 2 and 3 are factors of 6, as when multiplied with each other give us 6.

Now we can define the meaning of prime factorization, which is as follows:
Prime Factorization Definition: Prime factorization is a method of finding all the prime numbers which when multiplied with each other gives us the result of the original number given, whose factors are to be found.Note that each and every number greater than 1, can be expressed as the product of prime factors and hence, prime factorization is a method of reducing any number into its product of prime factors.

## Prime Factorization Methods

There are many methods for finding out the prime factorization of any number. Some of them are listed below:
Method Number 1:
The Trial Division Method for Prime Factorization:

This method is the most commonly used method in which the given number is divided by any least factor of the number and then again dividing the resulting number with some other factor, till we get the remainder zero.

Consider the prime factorization of 120 which is equal to 2 x 2 x 2 x 3 x 5, done by the division method as shown below:

Method Number 2:
The Factor Tree Method:

The factor tree method uses the concept of writing the factors in such a way that the choosing the simplest factor first and its corresponding factor on the top, and then further decomposing the rest of the factors again and again, writing one below the other, till all the factors become prime numbers.

For example:
consider the following factor tree of the number 24, as shown below:

Note that there are two factor trees for the number 24, but the set of prime factors of 24 is unique only. As 24 = 2 x 2 x 2 x 3, which can be expressed in exponent notation also, as 24 = 2^3 x 3. Thus, the set of prime factors of a number is always unique.

Method Number 3:
Algorithm based on Fermat’s Work: Also known as Fermat’s Algorithm:

This algorithm is based on the fact that if any given number can be written as the difference between their squares, then we can factorize the number as following:
This algorithm starts from the following steps:
Step 1.    Let n be a number whose prime factorization has to be done then, if
n = x2 – y2 = (x + y) * (x – y)
Step 2.  If n = a * b, where b $\geq$ a, then we can write x and y as x = $\frac{a + b}{ 2}$ and
$y$ =$\frac{b-a}{2}$
The main aim is to get that value of x and y such that n = x2 – y2, and hence we can start with the value of x as mod of square root of n.
Consider the following example of finding the prime factors of 12317, then following the above steps we would get:
Here the value of n is 12317.  Let the initial value of x be 111.  Now x2 – 4 = n, where 4 is the square of 2 and hence, the value of y will be 2. Hence, the prime factors of 12317 are, x - 2 and x + 2, which would come out to be 109 and 113, by putting the value of x.

Method Number 4:
Algorithm based on Euler’s Work:
Also known as Euler’s Algorithm: This algorithm is based on the fact that if any given number can be written as the sum of the squares of the two numbers.

## Prime Factorization Formula

For doing prime factorization of any number, we should know about the following important points:
1).    The numbers 1 and 0 are neither composite nor prime numbers and hence, they can never be a part of prime factors of any given number.
2).    Each and every number will always be factor of 0.
3).    The only number 1 will always has one and only one factor, which is one itself.
4).    To do prime factorization, we will keep on factoring the given number, until we figure out all the prime factors involved in it. If we have got a composite number, then we should remember that it can again be factorized further to get a prime factor again. Thus, the procedure of prime factorization only ends, whenever; we have found all its factors as prime numbers or factors.
5). The set of prime factors of a given number is always unique, that is the same set of prime numbers can not be used to factorize some other number. This statement is also known as the famous Fundamental Theorem of Arithmetic. As the multiplication of number is commutative, thus it does not matter in which order the factors are being multiplied.
Now we will list some of the important formulas of the prime factorization method which are listed below:
Formula 1:
The number of prime factors of a number is always found by adding one to the exponents of the prime factors, which are written in the exponent notation and then multiplying the adding number with each other.

For example: 72 can be prime factorized by giving us the prime factors as
72 = 23 x 32
Now, the value of exponent of 2 is 3, now adding 1 to 3 is 4.
Adding 1 to exponent of 3, which is 2 gives us 3.
Now multiplying 4 x 3 = 12. Hence, the total number of factors that number 72 has is 12, which is true as 1, 2, 3, 4, 6, 8, 9, 12, 16, 24, 36, and 72, are all the factors of 72, which if counted are 12 in numbers.

Formula 2:
Euler’s Formula:
This formula is based on the famous Euler’s Algorithm which starts from the following steps:
Step 1: Let n be an odd number whose prime factorization has to be done then, if
n = a2 + b2
Also assume that n can also be expressed as a sum of the squares of two other numbers such that,
n = c2 + d2
Step 2: Now, a2 + b2 = c2 + d2, this implies, a2 – c2  = d2 – b2 or
(a + c) (a - b) = (b + d) (b - d).
Step 3: If the Greatest common factor of a – c and d – b is k, then we will write,
a – c = k * l, d – b = k * m, and G.C.D of (l, m) is equal to1.
Step 4: Now, l and m are relatively prime numbers to each other, and hence, l (a + c) = m (d + b), and therefore, a + c is can be divided by m and hence,
a + c = m * n and d + b = l * n.
Step 5: Then n would be equal to $[(\frac{k}{2})^{2}+(\frac{n}{2})^{2}]$$(m^{2}+l^{2})$.

## Prime Factorization List

The following is the list of numbers starting from 1 to 100, along with their prime factorization:
 1 26 =  2 * 13 51 = 3 * 17 76 = 22 * 19 2 = 2 27 = 33 52 = 22 * 13 77 =  7 * 11 3 = 3 28 = 22 * 7 53 = 53 78 = 2 * 3 * 13 4 = 2 * 2 29 = 29 54 = 2 * 33 79 = 79 5 = 5 30 = 2 * 3 * 5 55 = 5 * 11 80 = 2 * 4 * 5 6 = 2 * 3 31 = 31 56 = 23 * 7 81 = 92 7 = 7 32 = 25 57 = 3 * 19 82 = 2 * 41 8 = 2 * 2 * 2 33 = 3 * 11 58 = 2 * 29 83 = 83 9 = 3 * 3 34 = 2 * 17 59 = 59 84 = 22 * 3 * 7 10 = 2 * 5 35 = 5 * 7 60 = 22 * 3 * 5 85 = 5 * 17 11 = 11 36 = 62 61 = 61 86 = 2 * 43 12 = 2 * 2 * 3 37 = 37 62 = 2 * 31 87 = 3 * 29 13 = 13 38 = 2 * 19 63 = 32 * 7 88 = 23 * 11 14 = 2 * 7 39 = 3 * 13 64 = 26 89 = 89 15 = 3 * 5 40 = 23 * 5 65 = 5 * 13 90 = 2 * 32 * 5 16 = 24 41 = 41 66 = 2 * 3 * 11 91 = 7 * 13 17 = 17 42 = 2 * 3 * 7 67 = 67 92 = 22 * 23 18 = 2 * 32 43 = 43 68 = 22 * 17 93 = 3 * 31 19 = 19 44 = 22 * 11 69 = 3 * 23 94 = 2 * 47 20 = 22 * 5 45 = 32 * 5 70 = 2 * 5 * 7 95 = 5 * 19 21 = 3 * 7 46 = 2 * 23 71 = 71 96 = 25 * 3 22 = 2 * 11 47 = 47 72 = 23 * 32 97 = 97 23 = 23 48 = 24 * 3 73 = 73 98 = 2 * 72 24 = 23 * 3 49 = 72 74 = 2 * 37 99 = 32 * 11 25 = 52 50 = 2 * 52 75 = 3 * 52 100 = 102

Similarly we can find the prime factorization of other numbers too, by just looking at the above table showing the prime factorization of first 100 numbers.
For example: the prime factorization of 101 would be 101 only because 101 is a prime number.
The prime factorization of 102 = 2 x 3 x 17.
The prime factorization of 103 = 103, and so on.

## How to Find Prime Factorization

Prime factoring a number involves breaking a number into its prime factors. Therefore to find any prime factorization of a number we will break it into its factor one by one, starting from the least possible factor that the given number could have.
The most commonly used method nowadays is the Factor Tree Method, which is explained below:
Consider the number 36, and we can make 36 as 2 times 18, which is equal to 36. Now we got two factors namely 2 and 18, out of which we can not break 2 into some other prime factor, and hence, we got 2 as one of the factors of 36. Now, we can break 18 a little further by breaking it into 2 times 9, and again we got another factor 2. Now 9, can again be factorized as 3 times 3, which are last factors, as 3 can not be reduced to other factors. Therefore, by combing all the factors, we get, 36 = 2 x 2 x 3 x 3, which is the prime factorization of the number 36, as 36 has been expressed as the product of prime numbers involving 2 and 3. This method is known as the factor tree method in which we write all the factors of a number in a tree format, circling all the prime numbers in the end which can be drawn as shown below:

Similarly, by using the factor tree method we can find the prime factors of 1092 = 2 x 3 x 2 x 7 x 13, as shown below:

In a similar manner we can find the prime factors of a given number by repeated division method in which we divide the number again and again till all the factors involved become prime factors.
Consider the prime factorization of 24 done by division method as shown below:

Thus, we found that 24 = 2 x 2 x 2 x 3. Hence, we got all the prime factors of 24.
The following are some examples of how to find prime factorization of a given number:
1). 39 = 3 x 13. Note that there are only two prime factors of 39, both of which are prime numbers.

2). 62 = 2 x 31. Note that there are only two prime factors of 62, one is 31, which is a prime number and the other is a 2, which is also a prime factor but 2 is an even number.

3). 64 = 2 x 2 x 2 x 2 x 2 x 2. Note that there are 6 prime factors; all are equal to 2, which is an even number.

4). 35 = 5 x 7. Note that there are only two prime factors of 35, both of which are prime number 5 and 7.
5). 22 = 2 x 11 . Note that there are only two prime factors of 22, both of which are prime numbers.

6). 32 = 2 x 2 x 2 x 2 x 2. Note that there are 5 prime factors; all are equal to 2, which is an even prime number.

## Prime Factorization with Variables

As we do the prime factorization of a number, in the similar way we can do factorization of a variable also, by writing their coefficients as the product of prime numbers and all the rest of the variables having exponent 1 or variables written with the power of 1.
Thus, a variable which is also known as a monomial in algebraic terms, (as its coefficient will always be at least one or more than that), can also be factorized, as the product of numbers, -1 and the variables with no powers or exponents greater than equal to one.

For example:
consider the following prime factorization of monomial which is a variable too, given as -6xy2.
Now the first thing would be to factorize its coefficient number which is equal to 6, and hence, -6 = -2 x 3. Hence, -2 and 3 are the factors of the variable too.
Now next thing is to factorize xy2 = x. y. y, as y has the power 2, and we have to write the variables as power equal to one only.
Hence, by combining all the factors together with the multiplication sign, we get:
-6xy2 = -2 . 3. x. y. y, which is the prime factorization of -6xy2.

The following are some examples of how to find prime factorization of a variable or variables:
1).81 z2: The prime factorization of this variable would be equal to
3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ z ⋅ z = 81 z2
2).    14 m: The prime factorization of this variable would be equal to 2⋅7⋅m = 14 m.
3).    92 ab: The prime factorization of this variable would be equal to 2⋅2⋅23⋅a⋅b
4).    8 a3b: The prime factorization of this variable would be equal to 2⋅2⋅2⋅a⋅a⋅a⋅b
5).    32 r3s5: The prime factorization of this variable would be equal to 2⋅2⋅2⋅2⋅2⋅r⋅r⋅s⋅s⋅s⋅s⋅s

Similarly, we can find the prime factorization of all other variables having higher powers.

To summarize, in simple words, we can say that for factoring any variable, we have to break its components into its coefficients, the sign of minus (-) if given, would be taken with the prime factorization of coefficient only. Then we will separate the variable components so that they can be written in multiplication form one after the other. Thus, prime factorization of variables also follows the same exact rule as in case of finding prime factorization of numbers too.

## Prime Factorization using Exponents

Exponents are known as the powers of any given number. And since we know that a number can be expressed as the product of its prime factors, so it is quite possible that we could have many prime factors which are repeating themselves many times. So instead of writing these factors individually again and again we can write them in exponent form, to make the factors written in a simpler way.

Consider the prime factorization of 40, and then we will get the following:
Thus, instead of writing 40 = 2 x 2 x 2 x 5, we can write these factors of 40 into their exponent form as 40 = 23 x 5, as 2 is appearing 3 times in the prime factorization of 40.
An exponent or power of a number shows that how many times the number is used being a factor for a particular given number.

The following are some examples of how to find prime factorization of a number written in exponent form:
1). 72 = 2 x 2 x 2 x 3 x 3. Note that in exponent form we will write the prime factorization of 72 = 23 x 32.

2). 30 = 2 x 3 x 5. In exponent form we will write the prime factorization of 30 = 21 x 31 x 51.

3). 27 = 3 x 3 x 3. In exponent form we will write the prime factorization of 27 = 33.

4).104 = 2 x 2 x 2 x 13. In exponent form we will write the prime factorization of 104 = 23 x 131.

5). 76 = 2 x 2 x 19. In exponent form we will write the prime factorization of 76 = 22 x 191.

6). 48 = 2 x 2 x 2 x 2 x 3. In exponent form we will write the prime factorization of 48 = 24 x 31

7).100 = 2 x 2 x 5 x 5. In exponent form we will write the prime factorization of 100 = 22 x 52.

8). 63 = 3 x 3 x 7. Un exponent form we will write the prime factorization of 63 = 32 x 71.

## Examples of Prime Factorization

The following is the list of some solved examples of prime factorization of numbers:
Example 1: Find the prime factors of the number 24 and express it as the product of prime factors by using the exponent notations.

Solution: By using the usual division method we found that:
24 = 2 x 2 x 2 x 3 = 2$^ 3$ x 3.
Hence, the exponent notation for the factors of 24 is equal to 23 x 31.

Example 2: Express each of the following number given below as the product of their prime factors by using any method of prime factorization and hence, write their prime factors. Use the exponent notation if the same factor is repeating more than one time.
1) 35
2) 112
3) 153
4) 145
5) 125
6) 172
7) 196
8) 189

Solution:
1) 35 = 5 x 7. Hence, the prime factors of 35 are 5 and 7.

2) 112 = 2 x 2 x 2 x 2 x 7. Hence, the prime factors of 112 are 2 and 7. Since, 2 is repeating 4 times, therefore, in exponent form we can write, 112 = 24 x 71.

3) 153 = 3 x 3 x 17. Hence, the prime factors of 153 are 3 and 17. Since, 3 is repeating 2 times, therefore, in exponent form we can write, 153 = 32 x 171.

4) 145 = 5 x 29. Hence, the prime factors of 145 are 5 and 29.

5) 125 = 5 x 5 x 5. Hence, the prime factor of 125 is 5 only. Since, 5 is repeating 3 times, therefore, in exponent form we can write, 125 = 53.

6) 172 = 2 x 2 x 43. Hence, the prime factors of 172 are 2 and 43. Since, 2 is repeating 3 times, therefore, in exponent form we can write, 172 = 22 x 431.

7) 196 = 2 x 2 x 7 x 7. Hence, the prime factors of 196 are 2 and 7. Since, both 2 and 7 are repeating 2 times, therefore, in exponent form we can write, 196 = 22 x 72.

8) 189 = 3 x 3 x 3 x 7. Hence, the prime factors of 189 are 3 and 7. Since, 3 is repeating 3 times, therefore, in exponent form we can write, 189 = 33 x 7.