# Postponed Prime Sieve in Swift

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 structs, 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" :-)

Replay

Category: primes Time: 2016-07-29 Views: 5