Why Prime number is interesting?
What make prime number interesting is because it's unique prime factors. Prime factor (or prime factorization) of a positive integer number is the prime product of that number.
N = p 1 x p 2 x ... x p n , where p i are prime numbers.
For example the prime factor of
27 = 3 x 3 x 3 100 = 2 x 2 x 5 x 5 12345 = 3 x 5 x 823 1234567 = 127 x 9721 123456789 = 3 x 3 x 3607 x 3803
Play around with the interactive program of Prime Factorization below. What are the prime factors of 12345678901234567890? What is the largest exponent? This interaction program determines the unique prime factors of an integer (canonical decomposition)
For simplest application of prime factor is to use it to ease division
1260 = 2 x 2 x 3 x 3 x 5 x 7
36= 2 x 2 x 3 x 3
Thus 1260 / 36 = 5 x 7 (after removing common prime factors)
Every integer has prime factorization. The nice property of prime factorization is its unique factors (after we sort the factors). This very nice property is also called fundamental theorem of arithmetic . Every positive integer can be written uniquely as a product of primes where the prime factors are written in ascending order of size. This unique format is also called canonical decomposition of a number.
24 can be written in many ways
24 = 1 x 24 = 2 x 12 = 3 x 8 = 4 x 6 = 2 x 2 x 6 = 2 x 3 x 4 and so on
However, if we use prime factor, there is only one prime factor that is
24 = 2 x 2 x 2 x 3
To obtain prime factors of a number larger than hundred, you may need to code it. In the next section, we will discuss algorithm to compute prime factorization