display | more...

The Fundamental Theorem of Arithmetic states that every positive integer (except 1) has a unique prime decomposition.

That is, each such number can be broken into a string of prime numbers, which, when multiplied together, yield the original number.

For example:

2 = 2
120 = 2 * 2 * 2 * 3 * 5

To get a number's prime decomposition, find the lowest prime number that divides it. Divide the original number by the prime, and then find the prime decomposition of the quotient.

As one might expect, the prime decomposition of a prime number is the number itself.

Of course, the same prime number can appear more than once in the prime decomposition of many numbers. For brevity, we express the repeats as an exponent of the prime in question. thus, 120 = (2^3)*3*5.

For 5280:

5280 = 2 * 2640
2640 = 2 * 1320
1320 = 2 * 660
660 = 2 * 330
330 = 2 * 165
165 = 3 * 55
55 = 5 * 11

So, the prime decomposition for 5280 is 2 * 2 * 2 * 2 * 2 * 3 * 5 * 11 or (2^5)*3*5*11.

Given that it's fairly easy to tell whether a number is divisible by the smallest primes (2, 3, and 5) you can get a certain way into most numbers without a lot of effort. As the primes get larger and larger, however, things get much more difficult. Most of modern cryptography is founded on the difficulty of factoring a number with only two prime factors.

If you want to try some numbers on your own, use a calculator or the factor program that comes with most UNIXes.