[Tutor] Re: Prime numbers

[Brett Leach]

This problem needs to be a little more closely defined. Are you trying to
find out if a particular number is prime, generate a list of the first n
primes, find all the primes less than n? Each of these problems lends itself
to optimization in different ways.

My favorite of these is to make a list of the first n primes. I like this
because the list itself is used as a tool while you make it. Start with a
short list of known primes:


from math import sqrt

primesList = [ 2, 3 ]

listLimit = 10000 #arbitrary limit

candidate = 5

while len( primesList ) < listLimit :
    factorLimit = sqrt( candidate )
    
    for factor in primesList:
        if factor > factorLimit: #then the number is prime
            primesList.append( candidate )
            break
            
        elif candidate % factor == 0: #then it is not prime
            break
            
        else:
            continue #iterate up the list of primes
    
    candidate += 2

for prime in primesList:
    print prime
    
> Message: 5
> From: ahimsa <ahimsa@onetel.net.uk>
> Reply-To: ahimsa@onetel.net.uk
> To: <tutor@python.org>
> Date: Mon, 24 Feb 2003 21:14:52 +0000
> Subject: [Tutor] prime numbers
> 
> Hello folks
> I am wanting to do an exercise that calls for a function to calculate pri=
> me=20
> numbers. I know that primes can *only* be divided by themself or by 1, an=
> d=20
> nothing else. My difficulty is translating this into parsimonious code=20
> without labouriously working out all the possible prime numbers as condit=
> ions=20
> for the if control.
> So far I have attempted % and /, and various combinations, but after a wh=
> ile I=20
> am almost including all the primes anyway. Can someone give me a nudge in=
> the=20
> right direction please.
> 
> Much appreciated
> AmF