Prime Numbers

Prime numbers are integers greater than 1 with no divisors except 1 and itself. All integers greater than one can be written as a product of some prime numbers. The first prime number is 2, then 3, and then 5, 7, 11, 13, and so on... It can be tedious to come up with prime numbers, so I plan on adding a prime number generator to this page. Until then, you can compute primes greater than 3 by hand by doing the following:

• For each n, take 4n + 1 and 4n + 3. We will now test these numbers for primality.
• For each of these numbers, take its square root (rounded down).
• For each prime candiate, try dividing it by each number from 2 up to the square root.
• If none of these divisions results in a whole number, the number is prime!

Example:

n = 3
4(3) + 1 = 13 and 4(3) + 3 = 17
⌊√13⌋ = 3 and ⌊√17⌋ = 4
13/2 = 6.5 and 13/3 = 4.333, neither of these are integers so 13 is prime!
Similarly, 17/2 = 8.5, 17/3 = 5.667, and 17/4 = 4.25. 17 is prime.

When n = 4, 4(5) + 1 = 21.
⌊√21⌋ = 4.
21/2 = 10.5, but 21/3 = 7. Since the result was an integer, 21 is not prime!

This method isn't perfect, which is why testing the numbers is required. This is a naive method for finding primes that doesn't really use many of the advanced techniques available to computers. As n grows bigger, it becomes more and more tedious to perform these computations by hand. Prime numbers are used extensively in cryptography, where the primes used can be arbitrarily large. The larger the prime, the more secure it is for use in cryptography.