Motivated by Unbounded Sieve of Eratosthenes in Swift, I looked out for other "infinite prime generators", i.e. functions which produce the list of prime numbers in increasing order and do not have an a-priori upper limit (such as the standard implementation of the Sieve of Eratosthenes). Repeated calling should produce "all" prime numbers (restricted only by time, available memory, and the limited range of the integer data type).

I found this answer (which was re-written for Python 3 later) to the SO question How to implement an efficient infinite generator of prime numbers in Python? and have implemented that "postponed sieve" algorithm in Swift (Swift 3, Xcode 8 beta 3 required):

`public final class PostponedPrimeIterator: IteratorProtocol { private var basePrimes: PostponedPrimeIterator! private var basePrime = 0 private var basePrimeSquared = 0 private var sieve: [Int: Int] = [:] private var initialPrimes = [2, 3, 5, 7] private var c = 9 // First candidate after fixed list public func next() -> Int? { if !initialPrimes.isEmpty { return initialPrimes.removeFirst() } if c == 9 { // Create the base prime generator and fetch the first odd prime: basePrimes = PostponedPrimeIterator() _ = basePrimes.next() basePrime = basePrimes.next()! basePrimeSquared = basePrime * basePrime assert(c == basePrimeSquared) } while true { defer { c += 2 } let factor: Int if let f = sieve.removeValue(forKey: c) { // `c` is divisible by `f` factor = f } else if c == basePrimeSquared { // `c` is the square of `p` factor = basePrime basePrime = basePrimes.next()! basePrimeSquared = basePrime * basePrime } else { // `c` is a prime number assert(c < basePrimeSquared) return c } // Insert next odd number which is divisiby by `factor` but not present in the sieve: var j = c + 2 * factor while sieve[j] != nil { j += 2 * factor } sieve[j] = factor } } } public struct PostponedPrimeSequence: Sequence { public func makeIterator() -> PostponedPrimeIterator { return PostponedPrimeIterator() } } `

The interesting thing about that algorithm is that the prime generator needs a list of "base primes" which are created using another instance *of itself.* This works because

- the base prime generator is created "delayed", after producing some fixed primes, and
- in order to generate primes up to \$ N \$, base primes are needed only up to \$ \sqrt N \$,

so that the creation of nested prime generators terminates eventually.

The sieving is done using a dictionary which holds the "next composite numbers" which are divisible by any prime less than the current base prime. As explained in the above-mentioned answer, the required memory to produce \$ n \$ primes is \$ O(\sqrt n) \$.

**Example usage** (first 20 primes):

`let p20 = Array(PostponedPrimeSequence().prefix(20)) print(p20) // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] `

**Benchmarking** (measure the time to compute the 1,000,000th prime number (on a 1,2 GHz Intel Core m5 MacBook):

`let TERMS = 1_000_000 let startTime = Date() var gen = PostponedPrimeIterator() for _ in 1 ..< TERMS { _ = gen.next() } let p = gen.next()! let endTime = Date() let time = endTime.timeIntervalSince(startTime) print(p, String(format: "%.02f", endTime.timeIntervalSince(startTime)), "sec") // 15485863 1.26 sec `

All kinds of **feedback** is welcome, including, but of course not limit to:

- Better type/property/variable names? I chose
`PostponedPrimeIterator`

because`Generator`

was renamed to`Iterator`

in Swift 3. - As far as I have seen, all iterators in the Swift standard library are
`struct`

s, i.e.*value types,*and Apple recommends to work with value types whenever possible. I needed to make it a`class`

because of the self-referencing property`private var basePrimes: PostponedPrimeIterator!`

Is there a better solution?

- Swift does not have a
`yield`

statement as in Python, which makes some kind of state machine necessary: The first primes are served from an array, then the base prime generator is created, and from then on the primes are produced by the sieving algorithm. Is there a more elegant way to manage these different states? Can making`basePrimes`

an implicitly unwrapped optional be avoided? -
`defer { c += 2 }`

is called in the main loop to increment the variable even if the loop was exited via`return c`

. Would you consider that a reasonable use? (http://nshipster.com/guard-and-defer/ seems to consider is "harmful" :-)