SwiftでInt型に素数かどうかまともに判定するメソッドを追加

SwiftでInt型に素数かどうか判定するメソッドを追加の実装がさすがにnaiveすぎるので。

• https://github.com/dankogai/swift-prime

SYNOPSIS

println(2.isPrime)                                // true
println(42.isPrime)                               // false
println(0x7FFFffff.isPrime)                       // true (M31)
println(0.nextPrime)                              // 2
println(Int.max.prevPrime)                        // 9223372036854775783 on OS X
println(Int.Prime.within(0..<100))                // [2, 3, 5, 7, ... 97]
println(Int.Prime.within(Int.max-100..<Int.max))  // [9223372036854775783]

DESCRIPTION

• 0...UInt.maxの範囲でまともな速度で判定します。
• 判定は軽く試し割りした後Miller-Rabin法で。後者は確率的アルゴリズムですが、判定対象の整数が充分小さければ決定的にもなるので、疑素数なしの判定をしています。
• その過程で(OS XのIntは64bitゆえオーバーフローを防ぐのに)128bit演算が必要となるのですが、その部分のみCで実装しています。clangは__uint128_tをサポートしているのですがSwiftはまだなので。ちょっと敗北感。Swiftで完結させる方法を緩募。
• GMPへのバインディングはすでに出来ることを確認しているのですが、GMP自体Yosemiteでバグがあるので、Bigintへの対応はTodoということで。
• Pure-swiftになりました。ただし128bit演算を使っていない分オーバーフローを防ぎながら少しずつ計算するので少し遅くなります。
• Swift 2に対応しました。
  • Linuxも対応しています。
  • Playgroundでも動きます。

Enjoy!

Dan.the.Prime.Programmer