A prime number is a number that has only 1 and itself as factors. The first primes are 2,3,5,7,11,13,17, ... All non-prime (i.e. composite) numbers can be split up into their prime factors. Here are the factorizations of the composite numbers missing above:
If given two large primes p and q, one can easily compute their product n = p * q. Until today, no efficient algorithms exist that decompose a product of two large primes into the prime factors, i.e. it takes "much longer" to factorize than to multiply. This fact is used for building cryptographic systems like RSA.
Last change: 2005-05-05