数学的なアルゴリズム

素数判定

枝刈りした探索

問題：ある数Nが素数であるか判定したい。

単純には全探索：1からNまで割り切れるか調べる

より効率的には：実はfloor(sqrt(N))まで調べて割り切れなければ素数だと考えてよい

アルゴリズムの正当性の証明：背理法で行う。

• 命題＝「Nが合成数であれば2以上sqrt(N)以下の約数が存在する」

1. 命題が成り立たないと仮定する。すなわちNが合成数で1以外の最小のNの約数Aがsqrt(N)を超えていると仮定する。

2. 約数の性質より、A*B=Nとなる正の整数Bが存在する。このときBはNの約数である。

3. しかしB = N / A < sqrt(N) であるため、仮定は棄却される

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本

エラトステネスの篩

エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズム エラトステネスの篩 - Wikipedia

アルゴリズム

1. 長さxの配列を用意し、1番目の要素にfalseを、2番目以降すべてにtrueを入れる

2. 配列の先頭から順に走査し、trueの要素を見つけたらその添字iを素数リストに追加し、配列のi^2以上のiの倍数番目をfalseにする。

3. 上記の篩い落とし操作を、走査している要素の添字がxの平方根に達するまで行う。

4. 最後までtrueだった要素の添字を素数リストに追加して処理終了。

自分の実装例

• i^2ではなくi*2以上にしている

import math

def eratosthenes(x: int) -> list:
    # 1. 長さxの配列を用意し、1番目の要素にfalseを、2番目以降すべてにtrueを入れる（1は素数ではないため）
    primes = []
    nums = [True] * x
    nums[0] = False
    # 2. 配列の先頭から順に走査し、trueの要素を見つけたらその添字iを素数リストに追加し、配列のi^2以上のiの倍数番目をfalseにする。
    for i in range(2, x+1):
        if nums[i - 1]:
            primes.append(i)
            for j in range(i ** 2, x + 1, i):
                nums[j - 1] = False
        # 3. 上記の篩い落とし操作を、走査している要素の添字がxの平方根に達するまで行う。
        # NOTE: 2から√nまでのforループにしてもよい
        if i >= math.sqrt(x):
            break
    # 4. 最後までtrueだった要素の添字を素数リストに追加して処理終了。
    for i in range(2, x+1):
        if nums[i - 1] and i not in set(primes):
            primes.append(i)
    return primes

eratosthenes(15)

[2, 3, 5, 7, 11, 13]