2以上の自然数を入力すると、ロー法によってその素因数分解が高確率で正しく出てきます。 https://turbowarp.org/1198169530?fps=250
＜ロー法とは？＞ 合成数Nに対して、Nの約数 (ただし1,Nを除く) を高確率で求めるアルゴリズムである。 具体的には下記の通り。 ① f(x) = x²+1 (mod N) 、初項 x₁ 、xₖ₊₁ = f(xₖ) という漸化式で定義された数列 xₖ を用意する。 ただし、x₁ は適当な自然数である。 また、i = 1 とする。 ② | xᵢ - x₂ᵢ | と N の最大公約数 d を求める。 ③ d = 1 のとき、i を 1 増やして②に戻る。 1 < d < N のとき、d は N の約数である。 d = N のとき、諦める。 ー補足ー ロー法にはない、このプログラム特有のルール。 x₁ を 1 ~ 100 までの自然数全てで試している。 これでも d = N であった場合、Nを素数とする。 2を因数に含むかの判定を独立して行っている。
