One of the first algorithms I implemented in Python was the prime sieve. I used it extensively when solving Project Euler problems as well. Good days :)
You can solve much more problems from Project Euler using a DFS variation of the Sieve of Euler. It is a depth first search of all the numbers less than n. It visits every number exactly once. When it visits a number, the prime factorization of the number is available (or any quantity derived from the factorization, like Euler's phi function).
