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()
    }
}

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]

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

private var basePrimes: PostponedPrimeIterator!