この記事について
- オイラープロジェクトの問題を解きながら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を実装
試し割りのアルゴリズムを用いています。
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番目の素数を取得できます
var iterator = PrimeNumberSequence().makeIterator()
for _ in (0..<10000) { let _ = iterator.next() }
let answer = iterator.next()!
print("answer is \(answer)")
PrimeNumberSequenceをCollectionに準拠させてはいけない
解答コードで使ったPrimeNumberSequence
をCollection
に準拠させるとどうなるでしょうか。
実際にやってみましょう。
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
の回数も増えているのが理由です。
公式ドキュメントの通り、Collection
のsubscript
の計算量はO(1)であることが期待されています。つまり、Collection
に準拠している限りは、subscript(1)
でもsubscript(100)
でも同じ時間で値が取れるべきですし、そのことを期待されているのです。
以上から、PrimeNumberCollection
は形式上はCollection
に準拠しているものの、Collection
に期待される要件を満たしていません。そのため、PrimeNumberSequence
をCollection
に準拠させてはいけないのです。