[Tutor] Tutor Digest, Vol 78, Issue 100 -- Prime numbers using square root of n

[Steven D'Aprano]

On Sun, 22 Aug 2010 03:47:21 pm Nick wrote:

> Thanks so much Steven.  I get it all except I don't think I see the
> pattern.  I see that we're already covering those higher factors
> since they're divisble by 2, 3, 5, etc.  I'm just not connecting the
> final dot with the square root of n.  It's almost there in my mind! 
> I just need a little more of a push!

Okay, let's consider an example: n = 100. We start checking factors of 
100 by dividing by 1, 2, 3, 4, ... and so on:

1 * 100 = 100
2 * 50 = 100
4 * 25 = 100
5 * 20 = 100
...

As the first factor increases, the second factor decreases 
proportionally. It has to, because the product is always 100. So, if 
you have one pattern going up (1, 2, 4, 5, ...), and another pattern 
going down (100, 50, 25, 20, ...), there must be a point where the two 
patterns cross! That point is at the square root:

10 * 10 = 100

Once you pass the square root, any factors you find will be the same as 
the factors you've already seen, only reversed:

20 * 5 = 100  # Seen this one before as 5*20.

Not all numbers have a whole number square root, but the principle still 
holds:


1 * 120 = 120
2 * 60 = 120
3 * 40 = 120
4 * 30 = 120
5 * 24 = 120
6 * 20 = 120
8 * 15 = 120
10 * 12 = 120
10.9545 * 10.9545 = 120
12 * 10 = 120  <=== already seen this one!



> Also I can write a program that 
> tests whether the number is a factor of 2, 3, 5, 7, but I think
> you're trying to point to me that this is cumbersome and not
> necessary.

Sort of. I'm not suggest that you create lists of multiples of 2, 3, 5, 
7 etc, and then cross off non-primes by checking to see if they are in 
one of those lists. That truly would be cumbersome and slow. But the 
two problems are similar. For simplicity, let's ignore 2 as a prime, 
and only think about odd numbers:

(1) For each odd number N between 3 and (say) 1000, check if it is a 
multiple of 3, 5, 7, 9, ... and IF SO, put it in the list "nonprimes".

versus:

(2) For each odd number N between 3 and (say) 1000, check if it is a 
multiple of 3, 5, 7, 9, ... and IF NOT, put it in the list "primes".


See, they are very nearly the same problem. The tricky bits are:

* dealing with 2 is a special case;

* you don't want to exclude (say) 3 from being a prime because it is 
divisible by 3; and

* you can stop testing at square-root of N.



-- 
Steven D'Aprano