How do you find prime factorization of a number?

Apr 12, 2016

Explanation:

To find prime factorization of a number, e have to first identify a prime number, which divides the given number. May times, it is easy if the number is divisible by $\left\{2 , 3 , 5 , 7 , 11 , 13\right\}$ and one can use divisibility rule for this purpose. However if number is $n$, one need to try a prime number only till $\sqrt{n}$. For details see this link.

Once a prime number is identified, as the number is a factor of given number, divide the number by this and find the quotient. Now try more prime factors of the quotient and go on till you find all the prime factors.

For example number $38115$ is divisible by $9$ (using divisibility test for $9$) and further it is also divisible by $5$, hence it will be divisible by $3 \times 3 \times 5$ or $45$.

Dividing $38115$ by $45$, we get $847$, which is divisible by $7$ and dividing this number by $7$ leads to $121$, whic is $11 \times 11$.

Hence prime factors of $38115$ are given by $3 \times 3 \times 5 \times 7 \times 11 \times 11$.