In Search of Primes

How do we find factors? The most basic and most obvious method of factoring, is dividing the number by possible factors and looking at the remainder. If the remainder is zero, the number is factorable by the test factor. There are other methods, but for the sake of argument and simplicity, we will stick with the division / remainder or modulo method as the math people call it( modulo is the math term for the remainder from a division).

What are good factors to test with? If you look back at the primer on primes, you can see that all of the composite numbers are factored with prime numbers. Coincidence? I don't think so. That is one of the other relationships between composite numbers and prime numbers. All composite numbers are products of prime numbers and only prime numbers. If you think about it, it will seem real obvious (maybe). So we only will use prime numbers as factor candidates.

When do we know we are done factor testing? Since the smallest useful prime number is 2, and the easiest tests are with smaller factors, it is a good place to start. One may or may not be prime, depending on your argument (I think it is prime), but that argument serves no point. Actually, since all even numbers are factorable by 2, this is a trivial test and we should move onto the next prime for our starting point. If we start by testing for the 3 factor, how high do we have to go to call it done? At first guess some would state the we should test from 2 to half the number being tested. That would not be a good guess. If a number is factorable it has to have at least two factors. And if we start out with 2, 3, 5, 7, 11, etc..., and all of these factors fail, then the largest possible factor would be that factor times itself. If the largest factor possible is a factor squared, the limit for factor testing would be the squareroot of the target number. So we test for factors with prime numbers from 3 up to the squareroot of the number under test.

So how many primes are there? Lots. Ok, more exactly, there are infinite number of primes. This was proven by some big, hairy proof that shows that the number of primes grows faster than the number of factors creates composites. What this really means it that there is no 'largest prime in the universe'. For every prime discovered, there is another bigger one. Lets look for something more interesting. In a certain range how many primes are there likely to be? In a given range of numbers the exact number of primes is going to vary, but some statistical guesses can be made. We can figure out that half of all numbers are factorable by 2, 1 out of 3 are factorable by three, and 1 out of 5 are factorable by 5, etc, etc. We can also figure out that some of these numbers are factorable by more than one factor. If we call the set of numbers not factorable to 2, P2, and the set of numbers not factorable to 3, P3, etc,etc. We have a number of sets, and the prime numbers are the intersection of these sets. The intersection for prime sets P2, P3, and P5 is defined by the following equation:

PS(5) = (1/2)*(2/3)*(4/5)

PS(5) = 8/30 = 4/15 = 26.66%

In case I just lost somebody, lets talk through this. If 1/2 of all numbers are not factorable by 2, and 2/3 of all numbers are not factorable by 3, then 2/3 of 1/2 are not factorable by 2 or 3. This is 2/6 or 1/3 of all numbers prime to 2 and 3. Now we can extend this by realizing that 4/5 of all numbers are not factorable by 5, therefore the set of numbers prime to 2, 3, and 5 is 4/5 of 1/3, or 4/15.

Keep in mind that this simple indicates the ratio of numbers prime to 5 over a statistically large range. If you want to go through the trouble to check my math, I have included a few of the prime set ratios for your pleasure.