To check if the number is prime, I'm using the following sub-function:
def check_prime(num): count = 0 for test in range(3, num, 2): if not test % num: count += 1 return count == 0
which I also rewrote as a simple list comprehension:
def check_prime2(num): test = [x for x in range(3, num, 2) if not x % num] return len(test) == 0
And in testing the difference in speed of the two functions is negligible - which is interesting because I was expecting the LC method to be a little faster.
I've never written a sieve before, so I could be doing it all wrong - I'm still tinkering with it. The main code is here:
import math def primes(max): limit = int(math.ceil(math.sqrt(max))) sieve = [x for x in range(3, max + 1, 2)] #print sieve for num in range(3, limit, 2): if sieve[(num - 3) / 2] and check_prime(num): # If its prime, knock out all multiples for i in range(num * 2, max + 1, num): if i % 2: sieve[(i - 3) / 2] = 0 final = [x for x in sieve if x > 0] return final
It doesn't bother making the first list (sieve) with any even numbers in it, and in its current state it also doesn't add the '2' to the start (this gets missed to avoid having any even numbers in the list at all - still thinking of a neat way to add this before the LC creates the list otherwise it needs to shift the entire list just to stick it in there). At this point its more about timing it and speeding it up rather than returning a correct list.
Yes, I could Google it - I'm more interested in opinions and ideas than someone elses code. Can anyone poke holes in how I've done it? Constructive criticism would be great, cheers