Postponed Prime Sieve in Swift

Motivated by this question, 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 this SO question 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  PostponedPrimeIterator {
        return PostponedPrimeIterator()
    }
}

The interesting t

Let me prefix this answer by a couple things:

• I only about 90% understand the algorithm in full. I know enough to tinker with it without breaking it, but I couldn't explain it to someone with pen and paper.

• As Swift 3 is still beta, some of the style guides are still up in the air. For the most part, I've tried to source purely stylistic comments from Apple's examples and documentation, but those might change and the community might end up with different ideas than Apple preached.

Now, addressing your points:


Better type/property/variable names?

I fully agree on PostponedPrimeIterator. It agrees with prexisting types, such as ClosedRangeIterator, DictionaryIterator, EnumeratedIterator, etc. The only variable I would potentially rename is private var c, to a more descriptive name of candidate (as your comment clarifies).


As far as I have seen, all iterators in the Swift standard library are structs.

As far as the reference page goes, it seems that the only classes in the standard library are Managed or non-@objc for the type system.


Is there a [way to make PostponedPrimeIterator a struct]?

I won't comment on whether this Iterator would be better as a struct or class: that's a bit philosophical and comes down to preference and your own benchmarks. However, if you do want to make it a struct, it is possible:

The reason that you cannot just make this a struct is that the compiler spits out the error error: value type 'Type' cannot have a stored property that references itself. The solution is to not directly recurse types, but to store a type-erased iterator.

The changes to use AnyIterator and structify PostponedPrimeIterator are these lines:

private struct PostponedPrimeIterator: IteratorProtocol {
    private var basePrimes: AnyIterator!

...

public mutating func next() -> Int? {
    ...
    if c == 9 {
        basePrimes = AnyIterator(PostponedPrimeIterator())
        ...
    }
    ...
}

In this manner you can get value semantics for your iterator. I made a micro benchmark to test the cost of wrapping a simple Array's IndexingIterator in an AnyIterator, which came out to about 0.006s per 10,000 items on my machine, so the cost is small but not negligible.

Again, I leave it up to you to decide if this is worth it: to me it feels like we are working against the compiler. If I am not mistaken, the reason for the compiler prohibiting simple property type recursion is that it can often lead to infinite space as each copy of the struct stores its own copy of the struct which stores its own copy of the struct which stores its own which leads me to my next point:


Can making basePrimes an implicitly unwrapped optional be avoided?

No, and the reason is as the above recursion tells us. If basePrimes is a non-optional type, then it has to be initialized at the initialization step. And since this is a copy of PostponedPrimeIterator in PostponedPrimeIterator, creating a value at initialization time would lead to infinite recursion and infinite space cost. Unfortunately as I cannot find the Apple reference on implicitly unwrapped optionals at this point, I will have to link a StackOverflow answer about them, which states:


Implicitly-unwrapped optionals are quite useful in cases where the value may not be present at initialization, but are set early and unlikely to become nil again.

This is the exact use-case that we have here, and as such I would say the implicitly unwrapped optional is the perfect tool to use.


defer { c += 2 }

This is a matter of style and your own tastes. What I find amusing is that this effectively is a return of C-style for loops, which were removed. For example, consider these two snippets of code:

Java:

int c = 3;
for ( /* no initialization */ ; /* no end case */ ; c += 2) {
    if ( isPrime(c) ) return c;
}

Swift:

var c = 3
while true {
    defer { c += 2 }
    if isPrime(c) {
        return c
    }
}

There is a slight difference, as in the Swift snippet the defer block runs after the return and it does not in the Java, but it would be trivial to use while { defer {} } to emulate a traditional C-style loop.

The point of showing that was to say that my first thought was a C-style for loop. This turns out to be correct, but I could have as easily intuited that the defer block only ran after a return and not just after the while block ended.

I feel the NSHipster article goes a little far in declaring that the defer {} return is in itself dangerous. I do agree, however, that when the defer's purpose is not immediately obvious from its context (such as when used for cleanup), it can be confusing. However, (and I'm sure an Apple example exists which I cannot find,) I think the use of defer right before a return is made clear in context. It is a bit different, but you can always see exactly when the code is going to run -- directly after the following

StackExchange Code Review Q#136332, answer score: 5