Swift Sieve of Eratosthenes

While watching the video for WWDC 2015 Session 414 - Building Better Apps with Value Types in Swift, I wanted to capture the Swift approach to the Sieve of Eratosthenes that was shown.

import Foundation

/// @param numbers must be an array of sequential numbers, not smaller than 2
func sieve(numbers: [UInt]) -> [UInt] {
    if numbers.isEmpty { return [] }
    let p = numbers[0]
    assert(p > 1, "numbers must start at 2 or higher")
    let rest = numbers[1..<numbers.count]
    return [p] + sieve(rest.filter { $0 % p > 0 })

func primesUpTo(max: UInt) -> [UInt] {
    return [1] + sieve(Array(2...max))


Minor Details

Further Reading

As they mention in the video, this implementation isn’t a true Sieve of Eratosthenes, because it walks over the whole array each time in the filter block, as opposed to only walking over the multiples of the prime number, and thus does more work than the true algorithm. You can read more details about this in “The Genuine Sieve of Eratosthenes” by Melissa O'Neill.