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))
}

print(primesUpTo(100))

Minor Details

• As you can maybe tell by the assert() I added, I was initially running into problems because I was starting the numbers array at 0 and then 1.

• A nice way to create an array from a range is Array(<range>).

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.