Primes are the "atomic" blocks of the natural numbers. Given the prime factors of a set of natural numbers, you can trivially computer the greatest common divisor and least common multiple. Primes are extremely important.

See http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...