On 25 апр, 13:29, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > 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
nice, but i'm a newbie to python too, so some things for me seems a liitle complicated))) -- http://mail.python.org/mailman/listinfo/python-list
