ELI5:What are prime numbers, and why are they so special/significant?

What are prime numbers?

They're numbers that are only perfectly divisible by themselves and 1. Perfectly divisible meaning that you get a whole number from dividing. For example, 6 is perfectly divisible by 2 (resulting in the whole number 3), and thus is not prime.

On the other hand, 3 is not perfectly divisible by 2 (which results in 1.5, obviously not a whole number). And any number larger than 3 will get a fraction between 0 and 1, and can't be a whole number. As a result, 3 is prime.

So here's some prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, and 1067441.

How do you determine that a number is prime?

Ah, there's the rub. There's no efficient way to determine if a number is prime. The only thing we can do is try all the possible divisors. So to find if a number, say, 1067441, is prime, we'd have to divide by 2, then 3, and so on. If there's no perfect divisors, it's prime.

There's a few ways to optimize this. For example, the Sieve of Eratosthenes is an algorithm to calculate all the prime numbers up to some larger number in a slightly more efficient way. It does this by eliminating some obviously not-primes. For example, any multiple of some number cannot be prime. So once we find that 2 is prime, we know that 4, 6, 8, and so on can't be prime, because they're multiples of another number (2).

What implication does this have?

As you can tell, this means that figuring out if a large number is prime is quite time consuming. Computers are able to figure this out quickly, but there's so many large primes that it's quite time consuming to find them. As a result, some encryption algorithms (eg, to password protect something) use the difficulty of calculating primes as a way to ensure that it's difficult to crack the encryption (and indeed, the only known way to crack the known secure forms of encryption is brute force: trying every possible key until one is the right one).

/r/explainlikeimfive Thread