Robert Berman wrote:
Greetings,
I am working on a 'simple' algorithm to solve the problem called PRIME1
explained at http://www.spoj.pl/problems/PRIME1/.
I do have an algorithm based on the Sieve of Eratosthenes and it does
work as I am failing the project not because of a computational error
but because of the dreaded TLE (time limit exceeded) designator. I have
determined there are at least 3 areas for improvement. The first is
within my code where I am creating a list of the first million primes.
The code is as follows:
def BuildSieve(itemsin):
TheSieve=list()
TheSieve = range(0,itemsin+1)
TheSieve[1]=0
for i in range(2,itemsin+1):
if (TheSieve[i] > 0):
j = i + i
while (j <= itemsin):
TheSieve[j] = 0
j+=i
return TheSieve
Observations:
By convention we like to use names beginning with CAPS for class names
and names beginning with lower for variable names. Not a requirement,
but it makes it easier for us to read the code.
There is no need for TheSieve=list() as the next statement overrides that.
There is no need to store the actual numbers in the list, as the list
index can serve that purpose.
You could instead build a list of 2 0s followed by all 1s: The Sieve =
[0,0] + [1]*(itemsin-2).
It is called with PrimaryList = BuildSieve(1000000)
I have read that list splicing rather than looping to set a range of
items to zero is the best approach. Given an example list of
In [53]: l1
Out[53]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Since 3 is a prime, we can eliminate all multiples of 3. Within l1,
these are expressed as
In [52]: l1[n+n:len(l1):n]
Out[52]: [6, 9, 12]
when n = 3. ( do know 12 would have been eliminated by the prime number
2)
It would be great if I could say l1[n+n:len(l1):n] = 0 but obviously
that will fail for obvious reasons. I am looking for the right hand side
of the statement to set a list within the list to all zeros. Also, if
anyone had a relatively simple explanation why in Python this is faster
than a loop, I would really like to understand it.
Thanks for the input.
Robert
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
--
Bob Gailer
Chapel Hill NC
919-636-4239
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
