Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Using Swift to demonstrate the Sieve of Eratosthenes
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) }) : []
}
}
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
}
}
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
}
}
}
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
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.