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