Prime Numbers

Prime numbers are the devil. Nothing is right about them, and nothing ever will be right about them. Simple laws that everybody can understand can easily be derived from them just by simple brainstorming.

For example:
Multiplying any two numbers (excluding 1) together gives a non-prime number.
Adding any two prime numbers (excluding 2) gives a non-prime number.

Those just came of the top of my head. The first one makes sense because if you have any equation a * b = c, the factors of c are always "1, a, b, c", along with any other factors of a or b. We have to exclude 1 because otherwise we get 1 * c = c, which is just multiplication's identity theorem.

The second takes a little more thought. Since we are excluding 2, that makes every other prime number an odd number. Given a and b as two prime numbers, they can be re-written as:

a = c + 1
b = d + 1

Where c and d are the even numbers directly before a and b, respectively. Now, if we add a and b together, using these new formulas, we get:

(c + 1) + (d + 1) = e
c + d + 2 = e

Because c and d are even, and they are being added with 2, an even number, this leaves e as an even number as well. And every even number is non-prime, with the exception of 2. However, no two prime numbers can add up to equal 2, so this is inconsequential.

However, the tricky part of prime numbers is trying to figure out whether the number is truly prime or not. By definition, a number is prime if and only if the only factors of the number are 1 and itself. So, surely the easiest way of determining whether a number is prime or not is simply to divide the number by every number between 1 and itself, noninclusive, and see if any of these numbers divide evenly into the test number. While yes, this does work, it takes linearly longer to do for each sequential number. By hand, this is very noticeable before you even hit 100. By computer, this is only noticeable when doing either a very large sample size of numbers, or testing for a very large number (such as the largest Mersenne Prime: 2^43112609 - 1).

So, there has to be a faster way of testing to see whether a number is prime or not. There are a few ways that I've thought of, or been shown, that help reduce the amount of time finding prime numbers.

First off, if the number is even, it's not prime. This may seem silly, but when you're checking to see how many prime numbers there are from 1 to 1000000000, it automatically cuts off half of your time.

Secondly, you don't have to check to see if there are any even factors to the number. For example, you don't need to check to see if 4 factors into 357, because 2 doesn't factor into this number, and if 2 doesn't factor in, 4, 8, or any other even number will not. Also, if any number doesn't factor in, any multiple of it also will not factor into the test number. However, this is harder to put into practice, because you essentially just start checking to see if the test value is prime by dividing it by prime numbers.

Finally, at least as far as I currently remember, the most helpful tool for finding primes by hand is to keep track of the results of dividing test factors. For example, say we are trying to find out if 25 is prime. Dividing 25 by 3 gives 8 1/3. Because of this, we never have to check factors higher than 8 1/3, because they are already ruled out. Let's do a real example with a real prime number:

Test number = 733

733/2 = 366.5
733/3 = 244.333
733/5 = 146.6
733/7 = 104.714
733/9 = 81.444
733/11 = 66.636
733/13 = 56.385
733/15 = 48.866
733/17 = 43.118
733/19 = 38.579
733/21 = 34.901
733/23 = 31.870
733/25 = 29.320
733/27 = 27.148
733/29 = 25.276

At this point, you can stop. To help clarify my previous paragraph, here's a generic formula:

test/x = y

Basically, if you are testing x sequentially, once y > x, you've already exhausted your options of factors. if you keep testing x higher than the first point at which y > x, y will always be some value between two previous x's. Alternatively, y will always be a non-integer value. Mind you, this holds true only if all of the previously tested x's gave a non-integer value for y.

I may rephrase paragraphs in this later if I feel I can explain things better. But for now, I think this is a good start.