Unityで素因数分解してみたのでメモ。
以前にミラーラビン判定法を使った素因数分解を javascript で実装した記憶があるけど、流用できなそうだし数学的なことは一切忘れたので愚直な方法で分解してみた。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
void Factoring(ulong n) { System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); ulong i = 2, t = n; List<ulong> factors=new List<ulong>(); while (i*i <= n)if(t%i == 0){ t/=i; factors.Add(i); }else{ i++; } if(t != 1){ factors.Add(t); }//last factor Debug.Log( n + "=" + string.Join("x",factors.Select(x => x.ToString()).ToArray()) ); sw.Stop (); Debug.Log(sw.Elapsed.TotalSeconds);//処理時間 } |
処理もわかりやすいし言うことがない。
今回初めて気づいたけど long がでかい。昔 long long とか使ってたような。
簡単な方法だと処理時間が犠牲になりそうなのでちょっと実験。
|
1 2 3 4 5 6 7 8 9 10 11 |
> Factoring((ulong)Mathf.Pow(2,32)); 4294967296=2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2x2 0.0050681 > Factoring(67280421310721); 67280421310721=67280421310721 0.0888738 > Factoring(12345678910111213); 12345678910111213=113x125693x869211457 1.1389114 |
まあ問題なさそう。
一応スマホ(P9 lite)でも測定してみる。
|
1 2 3 4 5 6 7 8 |
> Factoring((ulong)Mathf.Pow(2,32)); 0.0468953 > Factoring(67280421310721); 2.2538334 > Factoring(12345678910111213); 23.8668198 |
約数の少ない大きな数はちょっときつい。
機会があれば別の方法でもやってみたい。