素朴試し割り法

最終更新日:2003.04.17

IDM | 素因数分解 | 素朴試し割り法

目次

1. アルゴリズムの基本
2. Rubyによる実装
3. 改良
4. 計算量
5. 実装

アルゴリズムの基本

Nを次々と小さな素数で割っていくというアルゴリズムが考えられます。実際に除算を行なってみて、余りが0であれば素因数です。誰でも思いつく最も単純なものと言えるでしょう。

問題は、どのようにして素数を得るかと言うことです。素数を過不足無く列挙するような数列を何らかの演算式によって作る方法は発見されていません。

ある程度の大きさまでの素数であれば、エラトステネスの篩いなどの方法により予め素数表を作っておき、それを参照すればよいです。 しかしながら、巨大な素数を得るためにはそれなりの時間やメモリーが必要であり、結果を保持しておくためにもそれなりの容量が必要となります（詳細は、エラトステネスの篩いを参照してください）。

後述のように、このアルゴリズム自体、あまりに遅すぎて巨大な合成数の因数分解には適しません。どうせ小さな数の分解にしか使わないので、わざわざ素数表の作成に時間や記憶容量を費やすのも莫迦らしい話です。

そこで考えられるのは、多少の無駄を覚悟の上で、合成数も含めた全てのN以下の数で割って見るという方法です。

合成数m=pqはp, qよりも大きいため、mで試し割りを行おうとした時点では既にNの中のp因子, q因子は全て取り除かれています。このため、誤って合成数が素因数と判定されることはありません。

一番上に戻る

rubyによる実装

#!/usr/local/bin/ruby

n=ARGV.shift.to_i    # 第1引数より合成数を取得して数値オブジェクトに変換

result = []
p=2
while n!=1 do
  quot,rem = n.divmod(p)
  while rem==0 do    # 剰余が0である間、nをpで割り続ける。
    result.push p    # その都度、配列result末尾にpを付け加える
    n = quot
    quot,rem = n.divmod(p)
  end
end

print(result.to_s)   # 配列resultを文字列化して出力

一番上に戻る

改良

上記のプログラムではあまりにも思いつきそのままなので、もう少し改良してみたいと思います。

まず、Nの最大素因数が発見されてn==1になるのを待つ必要はありません。Nの平方根まで試し割りを行なえば、その時点で残っている商はそのまま素因数になります。

巨大な整数の平方根を求めるのは手間がかかります。しかしながら、どのみちこのアルゴリズムはあまり大きな数の分解には用いません。浮動小数点型を経由して平方根を求めれば精度は十分（すぎる）でしょう。

証明

mod 6で考えてみる

さて次に、2以外の偶数は全て合成数であるため、試し割りは2と奇数で行なえば十分であると言えます。

偶数（2の倍数）のついでに、3の倍数も素因数の候補から除いてみましょう。

6で割ったとき、余りが0,2,4のものは偶数であり、0,3のものは3の倍数なので、余りが1,5であるような数のみを考えればよいことになります。つまり、6n+1, 6n-1の形をした数のみ扱えばよいです。

以上を取り込んだプログラムを次に示します。

#!/usr/local/bin/ruby

def div_while_possible(result, n, p)
  quot,rem = n.divmod(p)
  while rem==0 do
    result.push p
    n = quot
    quot,rem = n.divmod(p)
  end
  n
end    


n = ARGV.shift.to_i

limit = Math::sqrt(n).to_i
result = []

n = div_while_possible(result, n, 2)
n = div_while_possible(result, n, 3)

p=5; q=7
while n!=1 do
  if p>limit then
    result.push n
    break
  end

  n = div_while_possible(result, n, p)
  n = div_while_possible(result, n, q)

  p+=6; q+=6
end

p result

これと同様に、5の倍数,7の倍数……を順次除いて計算するようにすれば、プログラムは複雑になるものの、精度は上がってゆきます。しかしながら、どんなに改良しても試し割り法自体が効率の良いアルゴリズムではないため、そこまでして改良する価値はないと言えるでしょう。

一番上に戻る

計算量

入力をnビットの整数とします。この整数Nは2ⁿ前後の数です。

上記の方法ではおよそ(√N)/3回の除算が必要であり、5,7,11,...の倍数を抜いたとしてもどのみち除算の回数は√Nのオーダーです。

O(√N)=O(2^n/2)回の除算が必要であるという結論になります。

一番上に戻る

実装

一番上に戻る

IDM | 素因数分解 | 素朴試し割り法