Little novice program written in Python
hellt
Dodin.Roman at gmail.com
Fri Apr 25 11:32:36 CEST 2008
On 25 апр, 13:29, Arnaud Delobelle <arno... at googlemail.com> wrote:
> hellt <Dodin.Ro... at gmail.com> 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)))
More information about the Python-list
mailing list