hellt <[EMAIL PROTECTED]> writes: > my variant of the sieve
Since you posted it, you are also looking for advice to improve your code ;) > def GetPrimes(N): > arr = [] > for i in range(1,N+1): > arr.append(i) This is the same as: arr = range(1, N+1) !-) > #Set first item to 0, because 1 is not a prime > arr[0]=0 > #sieve processing > s=2 remove this line > while s < math.sqrt(N): for s in xrange(2, int(math.sqrt(N))+1): > if arr[s-1] != 0: if arr[s-1]: > j = s*s remove this line > while j <= N: for j in xrange(s*s, N+1, s): > arr[j-1] = 0 > j += s remove this line > s += 1 remove this line > return [x for x in arr if x != 0] return filter(None, arr) Altogether now: def getprimes(N): arr = range(1, N+1) arr[0] = 0 for s in xrange(2, int(math.sqrt(N))+1): if arr[s-1]: for j in xrange(s*s, N+1, s): arr[j-1] = 0 return filter(None, arr) It's the same, but it looks a bit less like the litteral translation of some C code. Lastly, the lines: for j in xrange(s*s, N+1, s): arr[j-1] = 0 from above can be condensed using extended slices: arr[s*s-1 : N+1 : s] = [0] * (N/s - s + 1) (If I can count correctly) Giving the following, slightly shorter and probably faster: def getprimes(N): arr = range(1, N+1) arr[0] = 0 for s in xrange(2, int(math.sqrt(N))+1): if arr[s-1]: arr[s*s-1 : N+1 : s] = [0] * (N/s - s + 1) return filter(None, arr) If it was me, I would include 0 in the array, giving the slightly simpler: def getprimes(N): arr = range(N+1) arr[1] = 0 for s in xrange(2, int(math.sqrt(N))+1): if arr[s]: arr[s*s : N+1 : s] = [0] * (N/s - s + 1) return filter(None, arr) (I think) This all needs to be tested. -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list