エクセルVBAで実行時エラー７、メモリー不足が出ます。

質問

エクセルVBAで実行時エラー７、メモリー不足が出ます。
以下はVBAで素数を検索するコードです。
2億までは以下のように問題なく検索できました。

1億まで検索
素数の個数：5,761,455
上限値内の最大の素数：99,999,989
検索時間： 28.64063

2億まで検索
素数の個数：11,078,937
上限値内の最大の素数：199,999,991
検索時間： 59.34375

ところが3億にすると「実行時エラー７、メモリー不足」が出てしまいます。
これを回避する方法はないでしょうか？
エクセル2000、Win2000です。

システムのプロパティを見ると
Intel(R)　Celeron(R) CPU
420@ 1.60GHz
AT/AT COMPATIBLE
1,014,896,KB RAM

となっています。

コードは下記の通りです。

Sub Prime()
　　Const MX As Long = 300000000 '検索上限値（3億）
　　Dim flg(2 To MX) As Boolean 'フラグ配列
　　Dim cnt As Long, i As Long, j As Long, prm As Long
　　Dim t As Single

　　t = Timer
　　For i = 2 To MX '2から検索上限値までの間に
　　　　If Not flg(i) Then 'フラグがTRUEでなければ
　　　　　　For j = i + i To MX Step i 'その倍数（当然合成数）ごとに
　　　　　　　　flg(j) = True 'フラグをTRUEに
　　　　　　Next j
　　　　End If
　　Next i

　　For i = 2 To MX
　　　　If Not flg(i) Then 'フラグがTRUEでなければ
　　　　　　cnt = cnt + 1 '素数にカウント
　　　　　　prm = i '素数代入
　　　　End If
　　Next

　　Debug.Print "素数の個数：" & Format(cnt, "#,###") _
　　& vbNewLine & "上限値内の最大の素数：" & Format(prm, "#,###") _
　　& vbNewLine & "検索時間："; Timer - t
　　Erase flg '配列が占有していたメモリを解放

End Sub

回答No.6

zechs_gr-6 · ベストアンサー

どうやって計算量を減らすか結構悩みましたが、どうにか6n±1だけで判定するコードができました。
僕の環境では、これで22億ぐらいまで調べることができました。

Sub Prime3()
　　Const MX As Currency = 2200000000# '検索上限値
　　Dim buf(1) As Currency
　　Dim flg() As Byte 'フラグ配列
　　Dim limit As Long　　'配列のサイズ
　　Dim cnt As Long, prm As Currency
　　Dim i As Long, j As Long, k As Long
　　Dim t(2) As Single, tmp1 As Long, tmp2 As Long

　　t(0) = Timer
　　buf(0) = MX / 2
　　buf(1) = IIf(buf(0) > Int(buf(0)), MX, MX - 1)
　　buf(0) = buf(1) / 3
　　buf(1) = IIf(buf(0) > Int(buf(0)), buf(1), buf(1) - 2)
　　limit = Int(buf(1) / 3)

　　ReDim flg(1 To limit)　　'フラグ配列には6n±1の値のみを格納する
　　For i = 1 To Int(Sqr(MX)) \ 3 '5から検索上限値の平方根の間の6n±1の値
　　　　If Not flg(i) Then
　　　　　　tmp1 = i * 3
　　　　　　If i And 1 Then
　　　　　　　　k = (tmp1 + 4) * i + 1
　　　　　　　　tmp2 = tmp1 * 2 + 4
　　　　　　　　For j = k To limit Step tmp2
　　　　　　　　　　flg(j) = True
　　　　　　　　Next
　　　　　　　　For j = k + tmp1 - i + 1 To limit Step tmp2
　　　　　　　　　　flg(j) = True
　　　　　　　　Next
　　　　　　Else
　　　　　　　　k = (tmp1 + 2) * i
　　　　　　　　tmp2 = tmp1 * 2 + 2
　　　　　　　　For j = k To limit Step tmp2
　　　　　　　　　　flg(j) = True
　　　　　　　　Next
　　　　　　　　For j = k + tmp1 + i + 1 To limit Step tmp2
　　　　　　　　　　flg(j) = True
　　　　　　　　Next
　　　　　　End If
　　　　End If
　　Next

　　t(1) = Timer
　　cnt = 2　　 '素数2と3の分をあらかじめカウント
　　For i = 1 To limit
　　　　'フラグがTRUEでなければ素数にカウント
　　　　If Not flg(i) Then cnt = cnt + 1
　　Next

　　'最大の素数のみを調べる(最大の奇数から逆順に調べる)
　　For i = limit To 1 Step -1
　　　　If Not flg(i) Then
　　　　　　'素数代入
　　　　　　If i And 1 Then
　　　　　　　　prm = CCur(i) * 3 + 2
　　　　　　Else
　　　　　　　　prm = CCur(i) * 3 + 1
　　　　　　End If
　　　　　　Exit For
　　　　End If
　　Next
　　t(2) = Timer

　　Debug.Print "素数の個数："; Format(cnt, "#,###個")
　　Debug.Print "上限値内の最大の素数："; Format(prm, "#,###")
　　Debug.Print "素数判定："; Format(t(1) - t(0), "0.00000秒")
　　Debug.Print "カウント："; Format(t(2) - t(1), "0.00000秒")
　　Debug.Print "合　　計："; Format(t(2) - t(0), "0.00000秒")

　　Erase flg '配列が占有していたメモリを解放

End Sub

以下が22億での実行結果

素数の個数：107,540,122個
上限値内の最大の素数：2,199,999,973
素数判定：46.72656秒
カウント：22.75000秒
合　　計：69.47656秒

この掲示板、文字数制限きつ過ぎ…

お礼

先ほどは大変失礼いたしました。
ご教示のコードで以下のとおり１６億まで計算ができました。

素数の個数：79,451,833個
上限値内の最大の素数：1,599,999,983
素数判定：129.70310秒
カウント：51.20313秒
合　　計：180.90630秒

2と3以外の素数が6n±1になることや1バイトが8ビットであることは理解できますが、まだコードを理解できていません。
まだまだ勉強が必要だと痛感しています。
ありがとうございました。

回答No.7

zechs_gr-6

今朝からず～～～～っと「サポートで内容確認中」になっててnag0720さんの回答が見れなかったか
ら、僕はほとんど丸かぶりのコードを投稿しちゃったみたいですね。実行速度もほぼ同じでした。
僕の回答もいつ表示されるのやら。

Prime2とPrime3を1億までで実行するとこんな感じで、素数判定とカウントの部分に分けて比較して
みました。

(Prime2)
素数の個数：5,761,455個
上限値内の最大の素数：99,999,989
素数判定：2.96875秒
カウント：1.49219秒
合　　計：4.46094秒

(Prime3)
素数の個数：5,761,455個
上限値内の最大の素数：99,999,989
素数判定：1.90625秒
カウント：1.06250秒
合　　計：2.96875秒

素数判定とカウントのどちらもほぼ2/3になってました。
カウントが2/3になったのはフラグ配列の長さが1/2から1/3になったからでしょうね。
(1/3)/(1/2)=2/3だし。
素数判定が速くなったのは、3の倍数の位置のフラグを判定する必要が無くなったからだと思われます。

お礼

ご丁寧にありがとうございます。

回答No.5

nag0720

＃２です。
zechs_gr_6さんがフラグ配列を奇数だけにした場合をコーディングしてくれたので、
それを参考にして6n±1の場合を作ってみました。

Sub Prime3()
　　Const MX As Long = 300000000 '検索上限値
　　Dim flg() As Byte 'フラグ配列
　　Dim FlagSize As Long
　　Dim cnt As Long, i As Long, j As Long, prm As Long
　　Dim t As Single
　　Dim StartIndex As Long
　　Dim StepSize As Long

　　t = Timer
　　FlagSize = (MX \ 6) * 2
　　If FlagSize * 3 + 1 + (FlagSize Mod 2) >= MX Then FlagSize = FlagSize - 1
　　ReDim flg(1 To FlagSize)
　　For i = 1 To (Int(Sqr(MX)) \ 6) * 2
　　　　If Not flg(i) Then
　　　　　　If i Mod 2 = 1 Then
　　　　　　　　StepSize = i * 6 + 4
　　　　　　　　StartIndex = i * i * 3 + i * 4 + 1
　　　　　　　　For j = StartIndex To FlagSize Step StepSize
　　　　　　　　　　flg(j) = True 'フラグをTRUEに
　　　　　　　　Next j
　　　　　　　　For j = StartIndex + i * 2 + 1 To FlagSize Step StepSize
　　　　　　　　　　flg(j) = True 'フラグをTRUEに
　　　　　　　　Next j
　　　　　　Else
　　　　　　　　StepSize = i * 6 + 2
　　　　　　　　StartIndex = i * i * 3 + i * 2
　　　　　　　　For j = StartIndex To FlagSize Step StepSize
　　　　　　　　　　flg(j) = True 'フラグをTRUEに
　　　　　　　　Next j
　　　　　　　　For j = StartIndex + i * 4 + 1 To FlagSize Step StepSize
　　　　　　　　　　flg(j) = True 'フラグをTRUEに
　　　　　　　　Next j
　　　　　　End If
　　　　End If
　　Next i

　　cnt = 2 '素数2,3の分をあらかじめカウント
　　For i = 1 To FlagSize
　　　　'フラグがTRUEでなければ素数にカウント
　　　　If Not flg(i) Then cnt = cnt + 1
　　Next

　　'最大の素数のみを調べる
　　For i = FlagSize To 1 Step -1
　　　　If Not flg(i) Then
　　　　　　prm = i * 3 + 1 + (i Mod 2) '素数代入
　　　　　　Exit For
　　　　End If
　　Next

　　Debug.Print "素数の個数：" & Format(cnt, "#,###") _
　　& vbNewLine & "上限値内の最大の素数：" & Format(prm, "#,###") _
　　& vbNewLine & "検索時間："; Timer - t
　　Erase flg '配列が占有していたメモリを解放

End Sub

お礼

旅行に出かけており、お礼が大変おそくなってしまいました。
わたしの自宅のPC（XP Excel2003）では16億まで計算できました。

素数の個数：79,451,833
上限値内の最大の素数：1,599,999,983
検索時間： 226.7969

17億ではメモリー不足でした。

まだ内容を理解できていませんが勉強したいと思います。
ありがとうございました。

回答No.4

zechs_gr-6

>２以外の素数はすべて奇数ですから、フラグ配列を奇数の分だけにすればメモリは半分で済みます。
既に回答が出ているこの案を試してみました。
6n±1の案は、計算量をなるべく増やさずに済むような、うまい方法が思いつきませんでした。
当方の環境は CPU:Core2 Duo 2.4GHz、メモリ:4GBで、20億とかではメモリ不足になりましたが、
15億では問題なく実行できました。
ついでに、質問文のコードをいろいろ修正して高速化してます。

Sub Prime2()
　　Const MX As Long = 1500000000　　'検索上限値
　　Dim flg() As Byte 'フラグ配列
　　Dim half As Long　　'MXの半分
　　Dim cnt As Long, i As Long, j As Long, prm As Long
　　Dim t As Single, tmp As Long

　　t = Timer
　　half = IIf(MX And 1, MX, MX - 1) \ 2
　　ReDim flg(1 To half)　　'フラグ配列には3以上の奇数のみを格納する
　　For i = 1 To Int(Sqr(MX)) \ 2 '3から検索上限値の平方根の間の奇数
　　　　If Not flg(i) Then 'フラグがTRUE(i*2+1が合成数)でなければ
　　　　　　'(i*2+1)^2未満の値(合成数)は無視して検索上限値までi*2+1の奇数倍ごとに
　　　　　　'（ただし、べき乗や割り算を使わないように数式を変形）
　　　　　　tmp = i * 2
　　　　　　For j = i * tmp + tmp To half Step tmp + 1
　　　　　　　　flg(j) = True 'フラグをTRUEに
　　　　　　Next j
　　　　End If
　　Next i

　　cnt = 1　　 '素数2の分をあらかじめカウント
　　For i = 1 To half
　　　　'フラグがTRUEでなければ素数にカウント
　　　　If Not flg(i) Then cnt = cnt + 1
　　Next

　　'最大の素数のみを調べる(最大の奇数から逆順に奇数のみを調べる)
　　For i = half To 1 Step -1
　　　　If Not flg(i) Then
　　　　　　prm = i * 2 + 1 '素数代入
　　　　　　Exit For
　　　　End If
　　Next

　　Debug.Print "素数の個数：" & Format(cnt, "#,###") _
　　& vbNewLine & "上限値内の最大の素数：" & Format(prm, "#,###") _
　　& vbNewLine & "検索時間："; Timer - t
　　Erase flg '配列が占有していたメモリを解放

End Sub

15億での実行結果は以下のとおり。

素数の個数：74,726,528
上限値内の最大の素数：1,499,999,957
検索時間： 69.70313

ちなみに、当方の環境では元の質問文のコード(3億まで)でも問題なく実行できます。
また、質問者さんの環境では1億までで28秒程度のようですが、こちらの環境では15秒程度でした。
上記のPrime2を1億で実行すると、以下のとおり3倍ぐらい高速化できています。

素数の個数：5,761,455
上限値内の最大の素数：99,999,989
検索時間： 4.386719

ただし、僕が以前書いたHDDにデータを保存するコードでは、全ての素数を列挙してファイル出力ま
でやって、まだこれよりも若干速いので、無理して全ての処理をメモリ上でやる意味は無さそうです。

素数判定 2.41406秒
結果取得 1.60156秒
ファイル出力 0.22656秒
合計 4.26563秒
100000000までの素数は5761455個

お礼

旅行に出かけており、お礼が大変おそくなってしまいました。
わたしの自宅のPC（XP Excel2003）では16億まで計算できました。

素数の個数：79,451,833
上限値内の最大の素数：1,599,999,983
検索時間： 226.7969

17億ではメモリー不足でした。

まだ内容を理解できていませんが勉強したいと思います。
ありがとうございました。

補足

すみません。ANo.5さんへのお礼を間違ってこちらに書いてしまいました。
お許しください。

回答No.3

zechs_gr-6

以前、21億ぐらいまで素数を列挙するコードを書いたことがあるので参考に。
メモリが足りなくなったらHDDに退避するって手もあります。

参考URL：

http://park7.wakwak.com/~efc21/cgi-bin/exqalounge.cgi?print+200908/09080025.txt

お礼

ありがとうございます。
参考のサイト、勉強させていただきます。

回答No.2

nag0720

＞Dim flg(2 To MX) as Boolean 'フラグ配列 を
＞Dim flg(2 To MX) As Byte 'フラグ配列
＞に変えただけでメモリー不足にならず5億までは計算でききました。

変数のデータ型にはそれぞれ必要なバイト数が決まっています。
Booleanは２バイト、Byteは１バイトなので、
BooleanをByteに変えれば使用メモリ容量は半分になります。
また、数値型の０はFalse、０以外はTrueと解釈されるので、数値型はブール型として代用できます。
（数値型にTrueを代入すると－１になります）
なので、BooleanをByteに変えても文法的には問題ありません。

＃１の方法ですが、
１バイト＝８ビット
は分かりますか。
８ビットの各ビットをフラグとして代用すれば、１バイトで８個のフラグ配列として利用できます。
flg(i \ 8) And 2 ^ (i Mod 8))　や　(flg(j \ 8) Or 2 ^ (j Mod 8))　は、
配列要素の各ビットを操作する演算ですが、説明はちょっとしにくいので御自分で調べてみてください。
（\はバックスラッシュに見えているかもしれませんが、実際は円マークです）

メモリを節約する別の方法としては、
２以外の素数はすべて奇数ですから、フラグ配列を奇数の分だけにすればメモリは半分で済みます。
また、２,３以外の素数は6n±1型ですから、フラグ配列をその分だけにすればメモリは１／３で済みます。

お礼

> なので、BooleanをByteに変えても文法的には問題ありません。

了解です。
１バイト＝８ビットくらいはわかりますが、各ビットをフラグとして代用することがまだよくわかっていません。仰せのとおり調べてみます。
明日からしばし不在となるので、とりあえずお礼まで。
ありがとうございました。

回答No.1

nag0720

フラグ配列の確保でメモリ不足になったんでしょう。

メモリの節約方法としては、フラグ配列のタイプをByteにし、各ビットをフラグとして利用すれば、メモリは1/8で済みます。

ただし、\やModの演算に時間がかかるので、全体の処理時間は覚悟しておいたほうがいいでしょう。
（元の１０倍くらいかも）
\やModを使わない方法を工夫すればもう少し速くなるかもしれません。

Sub Prime()
Const MX As Long = 300000000 '検索上限値（3億）
Dim flg(MX \ 8) As Byte 'フラグ配列
Dim cnt As Long, i As Long, j As Long, prm As Long
Dim t As Single

t = Timer
For i = 2 To MX '2から検索上限値までの間に
If (flg(i \ 8) And 2 ^ (i Mod 8)) = 0 Then 'フラグがTRUEでなければ
For j = i + i To MX Step i 'その倍数（当然合成数）ごとに
flg(j \ 8) = (flg(j \ 8) Or 2 ^ (j Mod 8)) 'フラグをTRUEに
Next j
cnt = cnt + 1 '素数にカウント
prm = i '素数代入
End If
Next i

Debug.Print "素数の個数：" & Format(cnt, "#,###") _
& vbNewLine & "上限値内の最大の素数：" & Format(prm, "#,###") _
& vbNewLine & "検索時間："; Timer - t
Erase flg '配列が占有していたメモリを解放

End Sub

cnt = cnt + 1 '素数にカウント
prm = i '素数代入
の２行は始めのFor文の中に入れておきました。

もっと多くの素数を調べたいなら、フラグ配列を適当に分割してファイルに保存しながら処理していけば可能です。ただし時間は相当かかりますが。

お礼

ありがとうございます。
よくわからないのですが、わたしの提示したコードの
Dim flg(2 To MX) as Boolean 'フラグ配列 を
Dim flg(2 To MX) As Byte 'フラグ配列
に変えただけでメモリー不足にならず5億までは計算でききました。（10億では無理でしたが）

素数の個数：26,355,867
上限値内の最大の素数：499,999,993
検索時間： 350.75

ご教示の
For i = 2 To MX '2から検索上限値までの間に
If (flg(i \ 8) And 2 ^ (i Mod 8)) = 0 Then 'フラグがTRUEでなければ
For j = i + i To MX Step i 'その倍数（当然合成数）ごとに
flg(j \ 8) = (flg(j \ 8) Or 2 ^ (j Mod 8)) 'フラグをTRUEに
Next j
cnt = cnt + 1 '素数にカウント
prm = i '素数代入
End If
の部分ですが、よくわかりません。
なぜこれで素数と判定できるのかお教えいただければ幸いです。