プロが教える店舗&オフィスのセキュリティ対策術

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

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

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

ところが3億にすると「実行時エラー7、メモリー不足」が出てしまいます。
これを回避する方法はないでしょうか?
エクセル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

A 回答 (7件)

どうやって計算量を減らすか結構悩みましたが、どうにか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秒

この掲示板、文字数制限きつ過ぎ…
    • good
    • 0
この回答へのお礼

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

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

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

お礼日時:2010/06/20 17:09

今朝からず~~~~っと「サポートで内容確認中」になってて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の倍数の位置のフラグを判定する必要が無くなったからだと思われます。
    • good
    • 0
この回答へのお礼

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

お礼日時:2010/06/20 17:11

#2です。


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
    • good
    • 0
この回答へのお礼

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

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

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

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

お礼日時:2010/06/20 17:01

>2以外の素数はすべて奇数ですから、フラグ配列を奇数の分だけにすればメモリは半分で済みます。


既に回答が出ているこの案を試してみました。
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個

この回答への補足

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

補足日時:2010/06/20 16:59
    • good
    • 0
この回答へのお礼

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

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

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

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

お礼日時:2010/06/20 16:48

以前、21億ぐらいまで素数を列挙するコードを書いたことがあるので参考に。


メモリが足りなくなったらHDDに退避するって手もあります。

参考URL:http://park7.wakwak.com/~efc21/cgi-bin/exqaloung …
    • good
    • 0
この回答へのお礼

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

お礼日時:2010/06/13 22:18

>Dim flg(2 To MX) as Boolean 'フラグ配列 を


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

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


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


メモリを節約する別の方法としては、
2以外の素数はすべて奇数ですから、フラグ配列を奇数の分だけにすればメモリは半分で済みます。
また、2,3以外の素数は6n±1型ですから、フラグ配列をその分だけにすればメモリは1/3で済みます。
    • good
    • 0
この回答へのお礼

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

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

お礼日時:2010/06/13 22:17

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



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

ただし、\やModの演算に時間がかかるので、全体の処理時間は覚悟しておいたほうがいいでしょう。
(元の10倍くらいかも)
\や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 '素数代入
の2行は始めのFor文の中に入れておきました。


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

ありがとうございます。
よくわからないのですが、わたしの提示したコードの
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
の部分ですが、よくわかりません。
なぜこれで素数と判定できるのかお教えいただければ幸いです。

お礼日時:2010/06/12 13:43

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています