# Little novice program written in Python

Fri Apr 25 11:29:15 CEST 2008

```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
>     #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
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] =  * (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
for s in xrange(2, int(math.sqrt(N))+1):
if arr[s-1]:
arr[s*s-1 : N+1 : s] =  * (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 = 0
for s in xrange(2, int(math.sqrt(N))+1):
if arr[s]:
arr[s*s : N+1 : s] =  * (N/s - s + 1)
return filter(None, arr)

(I think)

This all needs to be tested.

--
Arnaud

```