オイラープロジェクトの問題を解きながらSwiftらしいコーディングを探る #2(問題7)

## この記事について

* オイラープロジェクトの問題を解きながらSwiftらしいコーディングを探ります。
* Swiftのバージョンは3.1を想定しています。
* この記事では問題7を解いていきます。

## #2なのに問題7なのはなぜ？
オイラープロジェクトの問題のうち記事にしやすそうな問題だけを取り上げているからです。

## 問題

### 原文
https://projecteuler.net/problem=7 より引用
> By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
> What is the 10001st prime number?

### 翻訳
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%207 より引用
> 素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
> 10001 番目の素数を求めよ.

## 解答の指針

素数を列挙するSequenceプロトコルに準拠した型を作りましょう。
また、Collectionプロトコルについても少し解説しています。

## 解答

### 素数の数列を表すSequenceを実装

試し割りのアルゴリズムを用いています。

```swift:PrimeNumberSequence
struct PrimeNumberSequence: Sequence {
    func makeIterator() -> PrimeNumberIterator {
        return PrimeNumberIterator()
    }
}

struct PrimeNumberIterator: IteratorProtocol {
    private var primeList: [Int] = []
    mutating func next() -> Int? {
        // 最初の素数は2
        guard primeList.count != 0 else {
            primeList = [2]
            return primeList.last!
        }
        // 2番目の素数は3        
        guard primeList.count != 1 else {
            primeList.append(3)
            return primeList.last!
        }
        
        let lastPrime = primeList.last!
        var primeNumberCandidate = lastPrime + 2 // 2以外の偶数は合成数なので飛ばす
        repeat {
            if primeList.contains (where: {
                primeNumberCandidate % $0 == 0
            }) {
                // 素数ではない
                primeNumberCandidate += 2
            } else {
                // 素数である
                primeList.append(primeNumberCandidate)
                return primeNumberCandidate
            }
        } while primeNumberCandidate <= Int.max - 2 // 桁あふれしないか確認する
        return nil
    }
}
```

### next()を10001回呼ぶと10001番目の素数を取得できます

```swift:answer
var iterator = PrimeNumberSequence().makeIterator()
for _ in (0..<10000) { let _ = iterator.next() }
let answer = iterator.next()!
print("answer is \(answer)")
```

## PrimeNumberSequenceをCollectionに準拠させてはいけない

解答コードで使った`PrimeNumberSequence`を`Collection`に準拠させるとどうなるでしょうか。
実際にやってみましょう。

```swift:PrimeNumberCollection
struct PrimeNumberCollection: Collection {
    private var primeList = [2, 3]
    let upperBound: Int
    
    init(upperBound: Int) {
        self.upperBound = upperBound
    }
    
    var startIndex: Int {
        return 0
    }
    var endIndex: Int {
        return upperBound
    }
    
    func index(after i: Int) -> Int {
        return i + 1
    }
    
    subscript(position: Int) -> Int {
        guard position < endIndex && position >= startIndex else {
            fatalError("Index out of bounds!")
        }
        
        guard position != 0 else {
            return 2
        }
        
        guard position != 1 else {
            return 3
        }
        
        var primeNumberCandidate = primeList.last! + 2
        repeat {
            if primeList.contains(where: {
                primeNumberCandidate % $0 == 0
            }) {
                primeNumberCandidate += 2
            } else {
                primeList.append(primeNumberCandidate)
            }
        } while primeList.count <= position
        return primeList.last!
    }
}
```

Collectionプロトコルに準拠したPrimeNumberCollectionを実装することができました。
実際に動いています。

```swift
let collection = PrimeNumberCollection(upperBound: 1002)
for prime in collection {
    print(prime) // 2, 3, 5, 7, ..., 29
}

print(collection[7]) // 19

print(collection[10001]) // 10001番目の素数
```

しかし、`PrimeNumberCollection`の様な型は__実装するべきではありません__。

### なぜCollectionに準拠させたらいけないか

理由は`subscript(n)`で__nの値が増えていくほど計算に時間がかかるからです__。上記コードを見ると分かりますが、`n`が増えるほど`repeat`の回数も増えているのが理由です。

[公式ドキュメント](https://developer.apple.com/reference/swift/collection/1641358-subscript)の通り、`Collection`の`subscript`の計算量はO(1)であることが期待されています。つまり、`Collection`に準拠している限りは、`subscript(1)`でも`subscript(100)`でも同じ時間で値が取れるべきですし、そのことを期待されているのです。

以上から、`PrimeNumberCollection`は_形式上は_`Collection`に準拠しているものの、`Collection`に期待される要件を満たしていません。そのため、`PrimeNumberSequence`を`Collection`に準拠させてはいけないのです。