プログラムは、プラットフォームWin64
64ビットでコンパイルしないと、計算に時間が掛かります。Win32モードだと、20倍以上の時間を要します。
素因数分解
素因数分解は、正の整数を素数の積で表すことです。
90 = 2 × 32 × 5
プログラムは簡単です。
１．偶数２で除算します。
２．割り切れたら、２の乗数の値を加算して、１．へ戻ります。
３．割り切れなかったら、奇数の素数の値の除算を３から始めます。
４．奇数３で除算します。
５，割り切れたら、３の乗数の値を加算して、４．へ戻ります。
６．割り切れなかったら、除数値を５＝３＋２の値にします。
７．奇数５で除算します。
８，割り切れたら、５の乗数の値を加算して、７．へ戻ります。
９．割り切れなかったら、除数値を７＝５＋２の値にします。
．
． 除数値２加算を繰り返します。
．
分解終了判別は、除算ごとにおこないます。
前の除算の商の値の平方根値より、除数値が大きくなったら分解終了です。
最後の商が１でない場合は、その値が、与えられた値の最後の素数値となります。
問題点
与えられた値が大きくなると、計算途中で、素数でない値の除算があります。
その為、計算に無駄な時間が発生します。
除数値が、２ずつしか増えないためです。
除数値がＰ＝ ２，Ｐ＝ ３，５，７，９，１１，１３，１５，１７，１９，２１，２３ ・ ・ ・ Ｐ＝Ｐ＋２
と変化します ９，１５，２１，は素数ではありませんが、９＝３X３，１５＝３Ｘ５，２１＝３Ｘ７ で既に素数で除算されていますので割り切れることはありません。
プログラムは、プラットフォームWin64
64ビットでコンパイルしないと、計算に時間が掛かります。
Win32モードだと、20倍以上の時間を要します。
プログラム
// プラットフォームが32の場合素数の値が32ビットを超える (p >= 2147483647) と演算が遅くなります。 // 64ビット推奨です。 // test1 9223372036854775806 = 2 × 3 × 715827883 × 2147483647 // test2 1537228672809129301 = 715827883 × 2147483647 // test3 6416582420042734637 = 6416582420042734637 // test4 9000000000000001121 = 9000000000000001121 // test5 15372286728550 = 2 × 5^2 × 31 × 337 × 29429093 unit Main; interface uses Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls, Vcl.ExtCtrls, System.Diagnostics; type TForm1 = class(TForm) Memo1: TMemo; LabeledEdit1: TLabeledEdit; Button1: TButton; Panel1: TPanel; procedure Button1Click(Sender: TObject); procedure prime_factorization(num: int64); private { Private 宣言 } AStopWatch : TStopWatch; procedure DisplayTime(msTime: Int64); public { Public 宣言 } end; var Form1: TForm1; implementation {$R *.dfm} // タイマー時間表示 procedure TForm1.DisplayTime(msTime: Int64); begin Panel1.Caption := Format('%5.3f ', [msTime / 1000.0]) + 'sec'; Panel1.Update; end; // 素因数分解 procedure TForm1.prime_factorization(num: int64); var cnt : int64; // 素数の乗数 i : int64; // 素数 snum : int64; // √num procedure Memoout; // 素数値表示 begin case cnt of 0: // cnt = 0 if num > 1 then Memo1.Text := Memo1.Text + inttostr(num); 1: // cnt = 1 i * 表示 if num > 1 then Memo1.Text := Memo1.Text + inttostr(i) + ' × ' else Memo1.Text := Memo1.Text + inttostr(i); else // cnt > 1 i^cnt * 表示 if num > 1 then Memo1.Text := Memo1.Text + inttostr(i) + '^' + inttostr(cnt) + ' × ' else Memo1.Text := Memo1.Text + inttostr(i) + '^' + inttostr(cnt); end; end; begin Memo1.Lines.Append('素因数分解'); Memo1.Text := Memo1.Text + ' ' + intTostr(num) + ' = '; // 偶数素数2の検索 偶数は2のみ i := 2; // 偶数素数2セット 除数 cnt := 0; // 乗数=0 while num mod i = 0 do begin // 余りが出るまで除数iで除算 inc(cnt); // 割り切れた数カウント num := num div i; // 除算 end; if cnt > 0 then begin // 乗数が0より大きかったら Memoout; // 検索素数値表示 cnt := 0; // 乗数=0 end; // 3以上の奇数の素数検索 最大値は√num以下 i := 3; // 奇数除数 初期値3セット snum := trunc(sqrt(num)) + 1; // √num while i <= snum do begin // iが√numより小さかったら実行 while num mod i = 0 do begin // 余りが出るまで除数iで除算 inc(cnt); // 割り切れた数カウント(乗数) num := num div i; // 除算 snum := trunc(sqrt(num)) + 1; // √num end; if cnt > 0 then begin // 乗数が0より大きかったら Memoout; // 検索素数値表示 cnt := 0; // 乗数=0 end; inc(i, 2); // 除数2加算 end; Memoout; // 最後の値表示 end; procedure TForm1.Button1Click(Sender: TObject); var num : int64; // 入力値 ch, cc : integer; s : string; begin val(labelededit1.Text, num, ch); // string->整数値 memo1.Clear; memo1.update; if ch <> 0 then begin // 変換エラーがあったら s := labelededit1.Text[ch]; // エラー文字取得 val(s, num, cc); // 文字ミスか値が大きすぎか確認 if cc <> 0 then // 文字のミスの場合 Memo1.Text := '入力値の' + intTostr(ch) + '文字目 ' + s + ' が間違っています。' else // 文字にミスなしの場合値大きすぎ Memo1.Text := '入力値が大きすぎます。'; exit; end; if num < 2 then begin Memo1.Text := '２以上の値にして下さい。'; exit; end; Button1.Enabled := False; AStopWatch := TStopwatch.StartNew; // タイマースタート DisplayTime(AStopWatch.ElapsedMilliseconds); // 時間表示 prime_factorization(num); // 素因数分解 AStopWatch.Stop; // タイマー停止 DisplayTime(AStopWatch.ElapsedMilliseconds); // 時間表示 Button1.Enabled := True; end; end.
prime_factorization.zip