[Tutor] Writing a prime number program using upper bound of square root of n

[Nick]

"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"

--------------------

Is there a way I can set my email program to insert the ">" symbol to mark what I'm replying to without manually doing it?

I get the picture now, that was a great example.  I wrote some code last night before going to bed that did what you were saying checking if it was divisible by 2, 3, 5, or 7.  I'm going to paste that.  
And so in my range function in this code could the upper bound be n*.5 instead of n+1 ?  is that how I would eliminate the checking of the repeated factors ?  I hope I'm not beating a dead horse guys.  thankis


primes = [2, 3, 5, 7]
def p(n):
    for i in range(3, n+1, 2):   
        if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
            pass
        else:
            primes.append(i)