[SciPy-user] prime numbers

[Stephen McInerney]

Walter, 
 
The culprit is the else: return 0 clause in your isdivisible() fn
You return 0 immediately if n is not divisible by the first entry listt[0]
i.e. 2. That's why you see all the odd numbers.
 
> def isdivisible(n,listt):> for i in range(len(listt)):> if (n%listt[i]==0):> return 1> else:> return 0
but you want this, where the 'return 0' is a fallthrough when all iterations of the for loop have failed to find any divisor:
> if (n%listt[i]==0):> return 1>
> return 0 # this is a fallthrough 
 
 
PS If you don't omit 1 from listt then you don't need to say listt[1:]
 
PPS another refinement to make this a proper Sieve of Eratosthenes
is that you only need to test up to sqrt(n) rounded down, i.e. int(math.sqrt(n))
Thus e.g. when you consider primeness of 31 you don't need to test if it's
divisible by all primes up to 29, only up to 5. This will speed things up a lot.
 
Regards,
Stephen
 
> Message: 9> Date: Thu, 23 Oct 2008 14:28:40 +0200 (SAST)> From: "Walter Mudzimbabwe" <walter at aims.ac.za>> Subject: [SciPy-user] prime numbers> To: scipy-user at scipy.org> Message-ID:> <60401.196.11.235.119.1224764920.squirrel at webmail.aims.ac.za>> Content-Type: text/plain;charset=iso-8859-1> > > can anybody help me figure out why the following program cannot produce> primes upto 10.> --------------------------------------------------> from scipy import *> > def isdivisible(n,listt):> for i in range(len(listt)):> if (n%listt[i]==0):> return 1> else:> return 0> > def primes_upto(m):> u=[1,2]> for i in range(3,m+1):> if (isdivisible(i,u[1:])==0):> u.append(i)> return u> > print primes_upto(10)> -----------------------------------------------------> it's output is:> > [1, 2, 3, 5, 7, 9]> > > > -- > Walter Mudzimbabwe (Formerly with AIMS)> University of Western Cape.> Mathematics Dept,> Private Bag X17,> 7535 Bellville,> RSA> > Contact :+27 78 5188402> mudzmudz at gmail.com
_________________________________________________________________
Want to read Hotmail messages in Outlook? The Wordsmiths show you how.
http://windowslive.com/connect/post/wedowindowslive.spaces.live.com-Blog-cns!20EE04FBC541789!167.entry?ocid=TXT_TAGLM_WL_hotmail_092008
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20081023/ed6d870b/attachment.html>