エラトステネス法

エラトステネス法で素数を列挙したり、与えられた整数を素因数分解したり約数を列挙したりします。

コンストラクタ

var es = initEratosthenes(n: int = 10000)

エラトステネス法のオブジェクトを作成します。サイズ$n$を指定すると$n$未満の整数についての配列を作ります。 これより大きい数についての下記のクエリが渡されたときは倍々に再構築されるので、範囲外アクセス等は気にせずに済みます。 したがって、ならしコスト$O(n)$となりますが、使うサイズが決まっている場合は最初からそのサイズで構築した方がオーバーヘッドが少なくて済みます。

素数判定

es.isPrime(n:int)

$n$が素数かどうかを判定する

計算量

• $O(1)$

素因数

es.primeDivisor(n:int):int

$n$の素因数を一つ返します

計算量

• $O(1)$

素因数分解

es.factor(n:int):seq[(int, int)]

$n$を素因数分解して素因数、指数の配列を返します

計算量 - 素因数の個数分の計算量がかかります

素数取得

es.getPrime(i:int):int
es[i: int]:int

インデックス$i$の素数を返します。つまり、小さい方から$i+1$番目の素数が返ります。

計算量 - ならしコスト$O(1)$です。

約数取得

es.divisor(n: int): seq[int]

$n$の約数を返します。