[Tutor] Tutor Digest, Vol 78, Issue 99 -- Prime numbers

[Steven D'Aprano]

On Sun, 22 Aug 2010 01:54:43 pm Nick wrote:

> I was interested in this specific topic as I've been working some
> problems on project euler. I've been trying to generate prime numbers
> as a first step to go about solving a problem.  I don't have a
> particular question about solving the problem, but want to ask about
> a relationship.
>
> The very first problem for projecteuler.net makes you write a program
> that finds all factors of 3 and 5 for n < 1000.  Were they trying to
> lead me down the path you're alluding to?  I'm not seeing the
> connection between that particular problem and finding primes.  I
> would appreciate more insight.  Thanks everyone!

Think about the definition of prime numbers. A number is prime if it has 
no factors other than itself and 1. (Except for 1, which is excluded by 
definition.)

So if you know that these numbers are divisible by 3:

3, 6, 9, 12, 15, 18, 21, ... 

and these numbers are divisible by 5:

5, 10, 15, 20, 25, 30, ... 

then you know that apart from the first number in each list (3 and 5) 
none of the other numbers could be prime. 12, for example, is not prime 
because it is divisible by 3 (also by 2), and 15 is not prime because 
it is divisible by 5 (also by 3).

More importantly, the code you write to detect *non-primes* will be 
quite similar to the code you write to detect primes. They're nearly 
checking the same thing:

If n is divisible by 3, then it goes in the "multiples of 3" list.
If n is divisible by 5, then it goes in the "multiples of 5" list.
If n is divisible by 7, then it goes in the "multiples of 7" list.
...

Compare that to primes:

If n is divisible by 2 (apart from 2 itself), then it is not a prime.
If n is divisible by 3 (apart from 3 itself), then it is not a prime.
If n is divisible by 4 (apart from 4 itself), then it is not a prime.
If n is divisible by 5 (apart from 5 itself), then it is not a prime.
If n is divisible by 6 (apart from 6 itself), then it is not a prime.
If n is divisible by 7 (apart from 7 itself), then it is not a prime.
...
Otherwise, if we get to n, and there are no other factors, then it is a 
prime.

But wait, this is doing too much work. If a number is divisible by 4, 
then it's also divisible by 2. Likewise if it is divisible by 6, 8, 10, 
12, ... any even number. So we eliminated all the even numbers (other 
than 2 itself) and there's no point in testing for divisibility by 4, 
6, 8, ...


If n is divisible by 2 (apart from 2 itself), then it is not a prime.
If n is divisible by 3 (apart from 3 itself), then it is not a prime.
If n is divisible by 5 (apart from 5 itself), then it is not a prime.
If n is divisible by 7 (apart from 7 itself), then it is not a prime.
...
Otherwise, if we get to n, and there are no other factors, then it is a 
prime.

We're still doing too much work. Why go all the way up to n? We know 
that (say) 93 can't possibly divide into 99, or 57 into 59. The largest 
number we need to check is the square root of n. The reason is a little 
subtle, so think about it, don't just take my word.

Hint: write down the factors of, say, 60: Can you see the pattern?

2*30, 3*10, 5*6, 6*5, 10*3, 30*2




-- 
Steven D'Aprano