Question

Express each number as a product of its prime factors: 104​

Answer 1

Answer:

Given any number  n  you can find its (unique) prime factorisation by repeated trial division by increasing prime numbers up to its square root  n−−√ . As soon as you have found a divisor,  p , you can replace  n  with  m=n/p  and continue the process of trial division with primes greater than or equal to  p  up to  n/p−−−√  (because you already know primes smaller than  p  will not divide  n/p ). The process terminates when the number is indivisible by any prime less than or equal to its square root because this implies the number is itself prime.

For the Natural Numbers up to one thousand a suitable list of primes is:

2,3,5,7,11,13,17,19,23,29,31  

For the number  45  the process is

2∤45  

3∣45⟹45↦45/3=15  

3∣15⟹15↦15/3=5  

3>5–√  so  5  is prime.

Thus the prime factors of  45  are  {3,5}  or

45=3×3×5=32⋅5  

For the number  2,585  the process is

2∤2585  

3∤2585  

5∣2585⟹2585↦2585/5=517  

5∤517  

7∤517  

11∣517⟹517↦517/11=47  

11>47−−√  so  47  is prime.

Thus the prime factors of  2,585  are  {5,11,47}  or

2,585=5×11×47=5⋅11⋅47  

This process works fine for small numbers, but becomes rather tedious for large numbers. In fact no efficient algorithm is known for factoring really large numbers although it is relatively easy to find large prime numbers. This asymmetry is why composite numbers created by multiplying two large prime numbers together are useful for encryption.