Little novice program written in Python
Arnaud Delobelle
arnodel at googlemail.com
Fri Apr 25 05:29:15 EDT 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]=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
More information about the Python-list
mailing list