Prime generator via unbounded Sieve of Erathosthenes

primes.py

"""Prime generator via unbounded Sieve of Erathosthenes.

Ported from http://wthwdik.wordpress.com/2007/08/30/an-unbounded-sieve-of-eratosthenes/
    
    For each prime number we store in a vector a pair consisting of
    the prime itself and a multiple, initialized to the prime number
    again. We compare each candidate with each multiple; if the
    multiple is smaller we increment it by the corresponding prime.
    Then if the candidate is equal to the multiple we discard it as
    it’s obviously a multiple of the current prime, otherwise we
    move on to the next prime; when there isn’t any prime left we
    have found another one and we append it to the vector.
    
    Thus this program performs the same operations as the
    traditional algorithm, but through a form of diagonalization
    it removes the original’s need for an upper bound.

Copyright (c) 2011 Erik Youngren

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

"""

def primes():
    """Prime generator via unbounded Sieve of Erathosthenes.
    
    """
    primes = [[2, 2]]
    candidate = 3
    
    while True:
        i = None
        for i in primes:
            while candidate > i[1]:
                i[1] = i[0] + i[1]
            
            if candidate == i[1]:
                break
        else:
            if i == primes[-1]:
                yield candidate
                primes.append([candidate, candidate])
        
        candidate = candidate + 1

I don't think if i == primes[-1]: is necessary — the else clause of the for loop will only execute if we didn't break. The only scenario in which we enter the else is when candidate is not multiple of any of the prime numbers, so we can yield it directly.