素数
Swift
Filter
関数型プログラミング
エラトステネスの篩

【swift】 1から100万未満の素数の和をエラトステネスの篩とfilter関数を使って求める。

先日、

【swift】 1から100未満の素数の和をforを使わずに求める。

というタイトルで投稿いたしました。

たくさんのコメントを頂き、ありがとうございました。

今回は、 1から100万未満の素数の和をエラトステネスの篩とfilter関数を使って求めました。

        let n = 1000000 //自由に変更してください。

let sqrtN = Int(sqrt(Double(n)))
var baseArray = Array<Int>(2 ... n)
var primeArray = [Int]()
while baseArray[0] <= sqrtN {
let firstPrime = baseArray[0]
primeArray.append(firstPrime)
baseArray = baseArray.filter{$0 % firstPrime != 0}
}
primeArray = primeArray + baseArray
let sum = primeArray.reduce(0, +)
print(sum)

print結果は、

37550402023

となります。(37550402023自体も素数です!)

計算時間は3.7秒でした。

n = 1000万にすると、総和は3203324994356で、計算時間は72秒、

n = 1億では、総和は279209790387276で、計算時間は1569秒でした。

(環境:MacBook Pro, 2018, 2.3GHz Intel Core i5)

解説:

baseArray: 2からnまでの全ての整数の配列です。

primeArray: 素数を集める配列。最初は空の状態です。

1. firstPrime: baseArrayの最初の数で、初めは「2」です。

2. primeArrayにfirstPrime (=2) を収納してから、

3. baseArray = baseArray.filter{$0 % firstPrime != 0} で2で割り切れない数だけを集めます。(エラトステネスの篩)

4. するとbaseArrayの最初の数は「3」となり、1. にループします。

baseArrayの最初が100万の平方根 (sqrtN = 1000) になるまで繰り返します。

1000以下の素数とfilterされた1000~100万までの素数を繋げれば出来上がりです。

baseArray = baseArray.filter{$0 % firstPrime != 0}

上記の部分をforとifで表現しようとすると結構面倒であり、filter関数の便利さを実感します。