Pebble Coding

プログラマーの作業メモ

swiftでフェルマーの素数定理をInt64の範囲内で確認してみる

最近、素数の本を読んで面白かったので、
フェルマー素数定理
任意のp:素数 n:自然数に対して、np - n を p で割った余りは 0 である。
をswiftで数値計算でInt64の範囲でいいから確認してみたい欲求に駆られ、実装してみました。

import Foundation

infix operator ** {} // <- (A)

/**
 * aのb乗
 */
func ** (a:Int64, b:Int64) -> Int64
{
    assert(b>=0)
    var v:Int64 = 1
    for _ in 0 ..< b {
        v *= a
    }
    return v 
}

/**
 * v:a未満の2以上のすべての素数のリスト
 * a:素数かどうか判定する値(2以上)
 */
func isPrime(v:[Int64], _ a:Int64) -> Bool {
    assert(a>=2)
    if a == 2 {
        return true
    }
    for i in v {
        // 余り
        let r:Int64 = a % i 
        if r == 0 {
            // 割り切れた
            return false
        }
    }
    // 割り切れないので素数
    return true
}

// 指定した値以下の2以上の素数のリスト
func primes(a:Int64) -> [Int64] {
    assert(a>=2)
    if a == 2 {
        return [2]
    }
    var v:[Int64] = primes(a-1)
    if isPrime(v,a) {
        v.append(a)
    }
    return v
}

// 1000以下の素数リストを表示
print(primes(1000))

// フェルマーの素数定理
// p:素数
// すべての自然数に対して、n^p - n を p で割った余りは 0 である
for p in primes(10) {
    for n in Int64(2) ... Int64(100) {
        let m = ((n ** p)-n) % p  
        print("n:\(n) p:\(p) n^p:\(n ** p) n^p-n:\((n ** p)-n) 余り:\(m)")
    }
}

工夫した点としては、整数を累乗する関数がswiftにはないので、自作する必要があります。
ここでは演算子オーバーロードする方法で解決してみました。
こんな機会でもないと使うときがありませんし。
**をオーバーロードするには(A)のように前方宣言が必要らしいです。
あとは特に難しいところはありません。
出力結果は、こんな感じになります。
色々な定理を簡単に確認できて便利ですね。

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
n:2 p:2 n^p:4 n^p-n:2 余り:0
n:3 p:2 n^p:9 n^p-n:6 余り:0
n:4 p:2 n^p:16 n^p-n:12 余り:0
n:5 p:2 n^p:25 n^p-n:20 余り:0
n:6 p:2 n^p:36 n^p-n:30 余り:0
n:7 p:2 n^p:49 n^p-n:42 余り:0
n:8 p:2 n^p:64 n^p-n:56 余り:0
n:9 p:2 n^p:81 n^p-n:72 余り:0
n:10 p:2 n^p:100 n^p-n:90 余り:0
n:2 p:3 n^p:8 n^p-n:6 余り:0
n:3 p:3 n^p:27 n^p-n:24 余り:0
n:4 p:3 n^p:64 n^p-n:60 余り:0
n:5 p:3 n^p:125 n^p-n:120 余り:0
n:6 p:3 n^p:216 n^p-n:210 余り:0
n:7 p:3 n^p:343 n^p-n:336 余り:0
n:8 p:3 n^p:512 n^p-n:504 余り:0
n:9 p:3 n^p:729 n^p-n:720 余り:0
n:10 p:3 n^p:1000 n^p-n:990 余り:0
n:2 p:5 n^p:32 n^p-n:30 余り:0
n:3 p:5 n^p:243 n^p-n:240 余り:0
n:4 p:5 n^p:1024 n^p-n:1020 余り:0
n:5 p:5 n^p:3125 n^p-n:3120 余り:0
n:6 p:5 n^p:7776 n^p-n:7770 余り:0
n:7 p:5 n^p:16807 n^p-n:16800 余り:0
n:8 p:5 n^p:32768 n^p-n:32760 余り:0
n:9 p:5 n^p:59049 n^p-n:59040 余り:0
n:10 p:5 n^p:100000 n^p-n:99990 余り:0
n:2 p:7 n^p:128 n^p-n:126 余り:0
n:3 p:7 n^p:2187 n^p-n:2184 余り:0
n:4 p:7 n^p:16384 n^p-n:16380 余り:0
n:5 p:7 n^p:78125 n^p-n:78120 余り:0
n:6 p:7 n^p:279936 n^p-n:279930 余り:0
n:7 p:7 n^p:823543 n^p-n:823536 余り:0
n:8 p:7 n^p:2097152 n^p-n:2097144 余り:0
n:9 p:7 n^p:4782969 n^p-n:4782960 余り:0
n:10 p:7 n^p:10000000 n^p-n:9999990 余り:0