This is the best algorithm I could come up with after struggling with a couple of Project Euler's questions.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

Can it be made even faster?

EDIT: This code has a flaw: Since numbers is an unordered set, there is no guarantee that numbers.pop() will remove the lowest number from the set. Nevertheless, it works (at least for me) for some input numbers:

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

EDIT: The rank so far (pure python, no external sources, all primes below 1 million):

1. Sundaram's Sieve implementation by myself: 327ms
2. Daniel's Sieve: 435ms
3. Alex's recipe from Cookbok: 710ms

EDIT: ~unutbu is leading the race.