Speed up this code?

[Kent Johnson]

aomighty at gmail.com wrote:
> I'm creating a program to calculate all primes numbers in a range of 0
> to n, where n is whatever the user wants it to be. I've worked out the
> algorithm and it works perfectly and is pretty fast, but the one thing
> seriously slowing down the program is the following code:
> 
> def rmlist(original, deletions):
>    return [i for i in original if i not in deletions]
> 
> original will be a list of odd numbers and deletions will be numbers
> that are not prime, thus this code will return all items in original
> that are not in deletions. For n > 100,000 or so, the program takes a
> very long time to run, whereas it's fine for numbers up to 10,000.
> 
> Does anybody know a faster way to do this? (finding the difference all
> items in list a that are not in list b)?

- Make deletions a set, testing for membership in a set is much faster 
than searching a large list.

- Find a better algorithm ;)

Kent