My backwards logic

[Chris Kaynor]

On Fri, Sep 5, 2014 at 2:49 PM, Seymore4Head <Seymore4Head at hotmail.invalid>
wrote:

> On Fri, 05 Sep 2014 12:48:56 -0400, Seymore4Head
> <Seymore4Head at Hotmail.invalid> wrote:
>
> >I'm still doing practice problems.  I haven't heard from the library
> >on any of the books I have requested.
> >
> >
> http://www.practicepython.org/exercise/2014/04/16/11-check-primality-functions.html
> >
> >This is not a hard problem, but it got me to thinking a little.  A
> >prime number will divide by one and itself.  When setting up this
> >loop, if I start at 2 instead of 1, that automatically excludes one of
> >the factors.  Then, by default, Python goes "to" the chosen count and
> >not "through" the count, so just the syntax causes Python to rule out
> >the other factor (the number itself).
> >
> >So this works:
> >while True:
> >    a=random.randrange(1,8)
> >    print (a)
> >    for x in range(2,a):
> >        if a%x==0:
> >            print ("Number is not prime")
> >            break
> >    wait = input (" "*40  + "Wait")
> >
> >But, what this instructions want printed is "This is a prime number"
> >So how to I use this code logic NOT print (not prime) and have the
> >logic print "This number is prime"
>
> I am sure this has already been done, but after it was pointed out
> that you don't need to test for any number that multiplies by 2 it
> made me think again.
>
> If you start with the list [3,5,7] and step through the list of all
> remaining odd numbers (step 2), and start appending numbers that won't
> divide by numbers already appended in the list, that would seem like a
> pretty efficient way to find all prime numbers.
>

To be correct, you only need to check for n being divisible by primes less
than sqrt(n). For example, the following code will produce a list of primes
from 2 to 1000 (the result will be in the "primes" list):

import math
primes = [2]
for i in range(3, 1000):
    end = math.sqrt(i)
    for x in primes:
        if x > end: # Once x is larger than the sqrt(i), we know it must be
prime, so we can early exit.
            #print(i, "is a prime number")
            primes.append(i)
            break
        if (i % x) == 0:
            #print(i, "is a composite number")
            break
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20140905/f59df312/attachment.html>