Using Swift to demonstrate the Sieve of Eratosthenes

Lucky Numbers.swift

import Foundation


/**
    Run an incremental counter, but return only the values that survive the "lucky number" process.

    The process is to list all the positive integers, then filter out entries in stages.  For all the numbers in a stage, let *N* be the first unfiltered number that is neither 1 nor been already been used as a filter seed for a previous stage, and filter out every Nth number.  The first pass uses 2 and therefore filters out every second number, i.e. the even numbers.  The second pass uses 3 and therefore filters out every third number that survived the 2-stage.  The third pass uses 7 and therefore filters out every seventh number that survived both the 2- and 3-stages.  The fourth pass uses 9 and therefore filters out every ninth number that survived the 2-, 3-, and 7-stages.  (Note that 2 is the only seed that eliminates itself in its filter.  Some definitions of lucky numbers avoid this irregularity by starting with the odd positive integers.)
 */
public struct LuckyNumberGenerator<Counter: IntegerType>: GeneratorType {

    /**
        The amount of lucky numbers found.  Retained so a new lucky number's every-Nth-time counter starts at the number's place in the list of lucky numbers.  (The filter starts counting one-past that since it starts running on the next turn.)
     */
    private var luckyNumberCount: Counter = 0
    /// The current positive integer to test (and possibly return).
    private var counter: Counter = 1
    /**
        Tests to filter every-Nth-item progressively.  Pre-seeded with the 2-stage to avoid the irregularity of its seed being eliminated by its own filter.
     */
    private var intervalCounters = [MultipleCounter<Counter>(factor: 2, nextCounter: 2)]

    public init() {
    }

    mutating public func next() -> Counter? {
        guard self.luckyNumberCount > 0 else {
            // First pass, special-cased so 1 isn't added as a filter.
            self.luckyNumberCount = 1
            return self.counter
        }

        outer: while true {
            // Go to the next trial number
            self.counter = self.counter.successor()
            // Check where the number is in each interval cycle
            for i in 0..<self.intervalCounters.count {
                if self.intervalCounters[i].next()! {
                    // The number hits this interval's every-Nth-time trigger, so it has to be skipped.
                    continue outer
                }
            }
            // The number survived all the every-Nth-time filters: it's lucky and gets its own filter.
            self.luckyNumberCount = self.luckyNumberCount.successor()
            intervalCounters.append(MultipleCounter(factor: self.counter, nextCounter: self.luckyNumberCount.successor()))
            return self.counter
        }
    }

    /// All the lucky numbers found so far.
    public var luckyNumbers: [Counter] {
        return self.luckyNumberCount > 0 ? self.intervalCounters.map({ $0.factor - (1 - $0.factor % 2) }) : []
    }

}

MultipleCounter.swift

import Foundation


/**
    Run an incremental counter but return, instead of the counter directly, whether it is a multiple of a given divisor.  The counter goes up by one for each call of `next`.
 */
public struct MultipleCounter<Counter: IntegerType>: GeneratorType {

    /// The divisor used for divisibility tests on the counter.
    public let factor: Counter
    /// The counter, secretly limited to `0..<factor`.
    private var modulus: Counter

    /**
     - precondition: `factor > 0`.

     - parameter factor: The divisor to test against the counter.
     - parameter nextCounter: The value to be tested on the first run of the `next` method.  Defaults to zero.

     - postcondition: The first return of `self.next()` is `factor` | `nextCounter` (i.e. if `factor` divides `nextCounter` exactly).
     */
    public init(factor: Counter, nextCounter: Counter = 0) {
        precondition(factor > 0)

        self.factor = factor
        self.modulus = nextCounter % self.factor
    }

    mutating public func next() -> Bool? {
        defer {
            self.modulus = self.modulus.successor()
            if self.modulus >= self.factor {
                self.modulus = 0
            }
        }

        return self.modulus == 0
    }

}

PrimeGenerator.swift

import Foundation


/**
    A generator for prime numbers.  The first call to `next` returns the first prime (2), and subsequent calls return subsequent primes.
*/
public struct PrimeGenerator: GeneratorType {

    /// The computer that finds the prime numbers
    private var sieve: SievePair

    /// Does default initialization
    public init() {
        self.sieve = SievePair()
    }

    public mutating func next() -> Int? {
        var results: (Int, Bool)
        repeat {
            results = self.sieve.next()!
        } while !results.1
        return results.0
    }

}

/**
    A generator for two primes at a time, with a given spacing between the pair.  If the spacing is even (and positive), there's probably an infinite number of pairs that can be found.  However, an odd spacing has at most one qualifying pair (2 and `spacing + 2`).
*/
public struct TwinPrimeGenerator: GeneratorType {

    /// Which algorithm to find paired primes to use
    private enum RunMode {
        case DoEvens
        case DoOdd
        case DoNoOdds
    }

    /// The computer that finds the prime numbers
    private var generator: PrimeGenerator
    /// The requested spacing between the returned primes
    public let spacing: Int
    /// Storage for the previous prime, to compare
    private var queue: (Int, Int)
    /// The run mode
    private var mode: RunMode

    /// - parameter x: The number to check.
    /// - returns: Whether `x` is prime.
    public static func isPrime(x: Int) -> Bool {
        guard x >= 2 else {
            return false
        }

        var pump = PrimeGenerator()
        var prime, quotient, remainder: Int
        repeat {
            prime = pump.next()!
            let qr = ldiv(x, prime)
            quotient = qr.quot
            remainder = qr.rem
            if remainder == 0 {
                return quotient == 1
            }
        } while quotient > prime
        return true
    }

    /// - precondition: `spacing > 0`.
    /// - parameter spacing: The desired distance between the members of a prime pair.  Defaults to two (i.e. "twin primes").
    public init(spacing: Int = 2) {
        precondition(spacing > 0)

        self.generator = PrimeGenerator()
        self.spacing = spacing
        self.queue = (2, 2)
        self.mode = spacing % 2 == 0 ? .DoEvens : .DoOdd
    }

    public mutating func next() -> (Int, Int)? {
        switch self.mode {
        case .DoEvens:
            repeat {
                self.queue = (self.queue.1, self.generator.next()!)
            } while self.queue.1 - self.queue.0 != self.spacing
            return self.queue
        case .DoOdd:
            self.mode = .DoNoOdds
            self.queue.1 += self.spacing
            return self.dynamicType.isPrime(self.queue.1) ? self.queue : nil
        case .DoNoOdds:
            return nil
        }
    }

}

Sieve.swift

import Foundation


/**
 Implements a version of the Sieve of Eratosthenes, used to discover prime integers up to a limit.  Since this class uses iteration instead of getting all the candidates at once, each integer is tested as it's reached by the incremental counter.  The counter goes up by one after each call to `next`.  The return value from `next` is whether the counter is a prime number.
 */
public struct Sieve: GeneratorType {

    /// The counter value used to generate the return value of a first call to `next`.
    public static let initialCounter = 1

    /// The counter to, well, count off iterations.
    private var counter: Int
    /// The square of the counter, samples needed to handle the queue of squares of primes.
    private var square: Int
    /// The difference to the next square.  Hopefully, adding this is quicker than calculating `counter * counter`.
    private var squareDifference: Int
    /// The list of primes found but pending to be added as a prime-counter.  Mapped with their square (as the key).
    public var pendingPrimes: [Int: Int]
    /// The list of primes currently used to mark off composites.
    private var primeCounters: [MultipleCounter<Int>]

    /// - postcondition:
    ///     - The first return from `self.next()` is the primality test for `initialCounter`.
    ///     - The counter starts at `initialCounter` and increments by 1 after each call to `next`.
    public init() {
        counter = self.dynamicType.initialCounter
        square = counter * counter
        squareDifference = 2 * counter + 1
        pendingPrimes = [:]
        primeCounters = []
    }

    mutating public func next() -> Bool? {
        var composite = self.counter <= self.dynamicType.initialCounter  // Not the FALSE literal so to special-case 1.
        //print("Checking \(self.counter) for primeness.")
        for i in 0..<self.primeCounters.count {
            let check = self.primeCounters[i].next()!
            composite = composite || check  // self.primeCounters[i].next()!
        }

        let prime: Int? = composite ? nil : self.counter
        if let newPrime = prime {
            self.pendingPrimes[self.square] = newPrime
            //print("Found a new prime: \(newPrime).")
        }

        self.counter = self.counter.successor()
        self.square += self.squareDifference
        self.squareDifference += 2
        if let root = self.pendingPrimes.removeValueForKey(self.counter) {
            self.primeCounters.append(MultipleCounter<Int>(factor: root, nextCounter: self.counter))
        }

        return prime != nil
    }

}

/**
    Implements a variant of the Sieve of Eratosthenes, where the `next` method returns the candidate prime and whether it passed it primality test together in a tuple (in that order).
 */
public struct SievePair: GeneratorType {

    /// The core sieve.
    public var sieve = Sieve()
    /// Track the value that the last primality test was for.
    private var counter = Sieve.initialCounter

    public init() {
    }

    public mutating func next() -> (Int, Bool)? {
        defer {
            self.counter = self.counter.successor()
        }

        return (self.counter, self.sieve.next()!)
    }

}

/**
    Implements the Sieve of Eratosthenes iteratively, but stores the qualification information differently.  For each prime found so far, store its next multiple to be found (starting from its square).  If a number is the next multiple for several primes, store them together.  The prime test is the number's presence in the dictionary, so each number is no longer tested by every single prime (at most its square root).
 */
public struct SievePair2<Counter: IntegerType>: GeneratorType {

    /// Iteration counter
    private var counter: Counter
    /// Square of the counter
    private var square: Counter
    /// Difference to next square
    private var squareDelta: Counter
    /// List of the next multiple for each prime, along with each known prime factor
    private var multiples: [Counter: Set<Counter>]

    /**
        - postcondition: The first call to `self.next()` returns 2 and its primality status.  Subsequent calls increase the number attribute by one (and set the Boolean attribute to that number's primality status).
    */
    public init() {
        self.counter = Counter.allZeros.advancedBy(1)
        self.square = self.counter * self.counter
        self.squareDelta = 2 * self.counter + 1
        self.multiples = [:]
    }

    public mutating func next() -> (Counter, Bool)? {
        self.counter = self.counter.successor()
        self.square += self.squareDelta
        self.squareDelta = self.squareDelta.advancedBy(2)

        if let primeFactors = self.multiples.removeValueForKey(self.counter) {
            // Got a composite; move its prime factors to their next multiples.
            for p in primeFactors {
                let nextComposite = self.counter + p
                if let previousPrimes = self.multiples.updateValue(Set(arrayLiteral: p), forKey: nextComposite) {
                    self.multiples[nextComposite]!.unionInPlace(previousPrimes)
                }
            }
            return (self.counter, false)
        } else {
            // Got a new prime!
            self.multiples[self.square] = Set(arrayLiteral: self.counter)
            return (self.counter, true)
        }
    }

}

extension SievePair2: CustomStringConvertible {

    public var description: String {
        var result = self.counter.description
        result += " ("
        var firstCompositeRun = true
        for x in self.multiples {
            if !firstCompositeRun {
                result += "; "
            }
            firstCompositeRun = false
            var firstPrimeRun = true
            for p in x.1 {
                if !firstPrimeRun {
                    result += ", "
                }
                firstPrimeRun = false
                result += p.description
            }
            result += " | \(x.0)"
        }
        result += ")"
        return result
    }

}