Take a number like 231. It can be factored as 3 x 7 x 11. But the factors 3, 7, and 11 can't be factored any further: they are prime numbers. Primes are to numbers as atoms are to molecules: the basic building blocks from which everything is constructed.
Here are the primes less than 100:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
There are twenty-five of them. Here are the primes between 10,000 and 10,100:
10007 10009 10037 10039 10061 10067 10069 10079 10091 10093 10099
There are eleven of them.
The primes seem to "thin out" as the numbers get bigger and bigger. This leads us to the question: do we ever run out of primes? Well, it turns out that there are infinitely many primes! This fact was discovered by the Greeks around 300 BC. The proof is found in Euclid's Elements.
It is not too difficult to factor small numbers like 123 or 1234567. But factoring larger numbers, like 1020030004000050000060000007, is more difficult. And the effort required rises very rapidly as the number of digits increases. On the other hand, it turns out to be easy, using some number theory, to find very large primes. Here is one:
It is a 1 followed by forty zeros followed by 63. It is easy to generate large primes like this, but difficult to break large numbers into primes. This is the basis of RSA cryptography.
Question. How do you know that 127 is a prime? What about a larger number like 882389? What about a really large number like
Integer factoring by Arjen Lenstra