エラトステネスの篩 - Wikipedia

学習を兼ねて書きました。

準備

計測には、下記記事のBenchmarkクラスをそのまま使います。
Swiftで重い処理の処理時間を測定する - Qiita

extension Array {   
    func reject(excludeElement: (T) -> Bool) -> [T] {
        return filter { !excludeElement($0) }
    }
}

実装

prime1

func prime1(n: Int) -> [Int] {
    var ns = Array(2...n)
    let upper = Int(sqrt(Double(n))) // maxの平方根
    return reduce((2...upper), ns) { (r: [Int], n: Int) -> [Int] in
        return r.reject {
            ($0 % n == 0) && $0 > n
        }
    }
}

prime1計測

Benchmark.measure("prime1") {
    prime1(200) // 0.971(s)
}

Swiftでも副作用を排除する関数型のアプローチで書ける！

只、prime1の実装だとUshio@githubさんがご指摘をしてくださった通り、問題点があります。

4（2の時点で落とされていたはずのもの）が計算されている
剰余が発生している

そこで、素直に副作用を許容して書いたのが下記です。

prime2

func prime2(n: Int) -> [Int] {
    var ns = Array(2...n)
    let upper = Int(sqrt(Double(n)))
    for i in 2...upper {
        let index = i - 2
        if ns[index] != 0 {
            for var j = index + i; j < ns.count; j += i {
                ns[j] = 0
            }
        }
    }
    return ns.filter { x in x != 0 }
}

prime2計測

Benchmark.measure("prime2") {
    prime2(200) // 0.190(s)
}

ベンチマークを取ってみると、prime1に比べてprime2の方が5倍近く早くなってますね!

まとめ

アルゴリズムの特性や性質を理解して、
素直に手続き型のアプローチで書いた方が可読性も高いし、速度も出るのなら
そちらを使うべしだし、適材適所だなと感じました。