Little novice program written in Python

[Arnaud Delobelle]

hellt <Dodin.Roman 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