LoginSignup
0

More than 5 years have passed since last update.

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

Posted at

この記事について

  • オイラープロジェクトの問題を解きながら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を実装

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

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番目の素数を取得できます

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

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

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

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を実装することができました。
実際に動いています。

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の回数も増えているのが理由です。

公式ドキュメントの通り、Collectionsubscriptの計算量はO(1)であることが期待されています。つまり、Collectionに準拠している限りは、subscript(1)でもsubscript(100)でも同じ時間で値が取れるべきですし、そのことを期待されているのです。

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0