Artanis · June 18, 2011 02:48 · vterron · Feb 24, 2015
diff --git a/primes.py b/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
	"""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