ここから本文です

エクセルで、素因数と約数を求めるマクロです。 自分で作ってみたのですが、添削...

aho_riekoさん

2011/10/520:15:52

エクセルで、素因数と約数を求めるマクロです。
自分で作ってみたのですが、添削をお願いします。

こちらのPCは intel Core(TM)i3 M330 2.13GHZ, RMA 4GB です。

Sub kiyaku_bunsuu()

Dim n, g, i, j
Dim lngCnt, lngCnt2 As Long
Dim MyArray(), SoArray()

'初期化
n = 0
i = 0
j = 0
lngCnt = 0

n = Cells(1, 1)

ReDim MyArray(1, 2000)

'最大公約数をチェックし、公約数が1の時、配列に格納する
For i = 2 To Sqr(n)
g = Int(n / i)
If g * i = n Then
MyArray(0, lngCnt) = i
MyArray(1, lngCnt) = n / i
lngCnt = lngCnt + 1
End If
Next i
'平方根まで求めた約数で、その上の約数を求める
i = 0
g = 0
j = 0
For i = lngCnt - 1 To 0 Step -1
g = MyArray(0, i)
j = n / g
If j <> g Then
MyArray(0, lngCnt) = n / g
MyArray(1, lngCnt) = g
lngCnt = lngCnt + 1
End If
Next i
'最後にその数そのものを格納
MyArray(0, lngCnt) = n
MyArray(1, lngCnt) = 1
'約数に1は含めていない

ReDim SoArray(2000)

g = 0
i = 0
j = 0
lngCnt2 = 0
'素因数を求める処理
If lngCnt >= 1 Then
lngCnt2 = 0
SoArray(0) = MyArray(0, 0)
n = MyArray(1, 0)
'約数を配列に格納しながら、次の約数を求める
For i = 2 To Sqr(n)
g = Int(n / i)
If g * i = n Then
lngCnt2 = lngCnt2 + 1
SoArray(lngCnt2) = i
n = n / i
i = 1
End If
Next i
'最後に1より大きい数が残ったら配列に格納
If n > 1 Then
lngCnt2 = lngCnt2 + 1
SoArray(lngCnt2) = n
End If
End If


'結果をワークシートに貼り付ける
If lngCnt = 0 Then
Cells(3, 2) = "素数です"
Cells(5, 1) = "素因数"
Cells(5, 2) = "約数"
Cells(5, 3) = "除算商"
Cells(6, 1) = MyArray(0, 0)
Cells(6, 2) = MyArray(0, 0)
Cells(6, 3) = MyArray(1, 0)
Else
Cells(3, 1) = lngCnt2 + 1
Cells(3, 2) = "個の素因数です"
Cells(4, 1) = lngCnt + 1
Cells(4, 2) = "個の約数です"
Cells(6, 1) = "素因数"
Cells(6, 2) = "約数"
Cells(6, 3) = "除算商"

i = 0
For i = 0 To lngCnt
Cells(i + 7, 2) = MyArray(0, i)
Cells(i + 7, 3) = MyArray(1, i)
Next i

i = 0
For i = 0 To lngCnt2
Cells(i + 7, 1) = SoArray(i)
Next i
End If

End Sub

補足実行時間短縮のため、ちょっと工夫しており、分かりにくいかもしれません。

現在のところ、EXCEL2007で、エクセルシート上の上限である
999兆9999億9999万9999
を計算させると、約9秒でした。

また、前回の質問で回答くださった kusa_kusa_kusa_kusaさんも
よろしくお願いします。

閲覧数:
901
回答数:
1

違反報告

ベストアンサーに選ばれた回答

編集あり2011/10/716:32:23

私が使っているかなり古いノートPC(*)で上記のコードを実行してみたところ以下のような実行時間でした。
(*)CPU:Intel Core Duo T2300(1.66GHz) RAM:2GB(空き 約1.5GB) Excel 2003(SP3)
<計測方法>
・Application.ScreenUpdatingをFalseにし、セルへの出力による実更新を抑制(計測後、実更新する)
・処理開始前に Timerの値を保持し、処理終了後に Timer - 保持した値を計算

※元のコードは確保している配列の要素が 2000であるため、確保する領域を予め広げてから実行しました。
========================================================================
パターン1(大きい値)
n=999999999999999(素因数:8, 約数:128)
<結果>
8個の素因数です
127個の約数です
平均 16.07秒

パターン2(約数の数が多い値)
n=586930569825600=(2^6)*(3^5)*(5^2)*(7^2)*11*13*17*19*23*29(素因数:21, 約数:24192)
<結果>
21個の素因数です
24191個の約数です
平均 14.92秒

※当初はn=563453347032576000=(2^12)*(3^6)*(5^3)*(7^2)*11*13*17*19*23*29
(素因数:29, 約数:69888)という値で計測し、
<結果>
29個の素因数です
70425個の約数です
平均 504.65秒
という結果を得たのですが、そもその nの値が精度の上限を超えていたようで
誤った計算結果が出てしまいましたので小さい値で計測し直しました。
(セルで表示できたから大丈夫と思ったのですが...)
========================================================================

で、パッと見た限りですが、
1.無駄と思われる(ループ)処理が多いように見える
2.変数のデータ型がバリアント型のため、オーバヘッドが大きい
のが気になりました。

2.については、長い桁の数をバリアント型の変数に格納しても内部的には倍精度
浮動小数点型(Double)になるので、バリアント型よりもデータ型を固定した方が
当然処理速度は向上します。
(最初から浮動小数点型による演算リスクは受入れることにしてます)

試しに変数のデータ型だけを lngCnt, lngCnt2を Long型、それ以外の変数を
Double型にして実行したところ、パターン1では平均 6.78秒、パターン2では
平均 7.79秒に短縮されました。(当初の数のときは 平均 208.9秒に短縮されました。)

ちなみに私も雑な実装(**)で作成し実行してみましたが、同環境で以下のようになりました。
(1も約数に含めてます)
========================================================================
パターン1:n=999999999999999のとき
<結果>
8個の素因数があります
128個の約数があります
平均 0.04秒

パターン2:n=586930569825600のとき
<結果>
21個の素因数があります
24192個の約数があります
平均 2.34秒
========================================================================
(**)
・素因数分解を行い、その素因数分解の結果より約数を列挙する。
・約数の昇順ソートは Excelの機能を利用する。

どうやら、今のコードだとデータの持ち方やアルゴリズム等を改良する余地が
十二分にあると言えそうです。

---
質問者ID:aho_rieko

質問した人からのコメント

2011/10/7 18:23:10

降参 variant型をdouble型にするだけで、倍速になりました。

なお、ソースを全部書くと1000文字超えるので、タイマーは省略しています。

アルゴリズム全体を再構成してみます。
ありがとうございます。

ちょい足しを取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

ID/ニックネームを選択し、「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問や知恵ノートは選択されたID/ニックネームのMy知恵袋で確認できます。

ほかのID/ニックネームで利用登録する