上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

えー、前からちょこちょこやっていた素数判定プログラム in ExcelVBAがとりえあず一旦まとまったので。 ここでソースコードを公開。

本当はExcelシートを置きたかったんだけれども、FC2ブログで書庫がアップロードできないので 方法を考え中であります。どうしようかな。

では、以下ソースコード

Sub 素数判定()
	Dim 対象 As Double
	Dim i As Double
	
	対象 = Cells(2, 1)
	
	If 対象 <= 3 Then
		MsgBox "素数"
	Else 
		If 対象 Mod 2 <> 0 Then
			For i = 3 To Sqr(対象) Step 2
				If i > 5 Then
					Do While i Mod 3 = 0 Or i Mod 5 = 0
						i = i + 2
					Loop
				End If
				If 対象 Mod i = 0 Then
					MsgBox "素数ではない。"
					Exit Sub
				End If
			Next
		Else
			MsgBox "素数ではない。"
		End If
	End If
End Sub

えー、さて。数点明らかになんだそれ的なところがあるので補足説明しておきます。
・対象=Cells(2,1)
 実際に作ってあるシートではセルA2に判定する対象の値を入れてもらって、
 判定ボタンを押すと判定する仕様なので、セルA2を代入してます。

・For i = 3 To Sqr(対象) Step 2
 Sqr()というのは平方根の関数です。簡単に言えば√
 例えばSqr(4)であれば、2が返ってくる。

・Mod演算子
 Mod演算子はVisual Basicで使える演算子で他の言語でいう%演算子と同じ意味です。
 いわゆる、余剰演算子。

あと、愚直に1から対象の値まで試し割りするよりも高速に計算が完了するよう工夫がしてあるのですが
説明するとプログラム云々というより数学の話になるので、詳細は記事の追記部分に書いておきます。

気になる方だけどうぞ。


では、どのように計算回数を減らしたかについて書きます。

まず初めに偶数の最小である素数「2」と奇数の最小である素数「3」を既知とします。
なので、対象の値が3以下であれば即時”素数”だと判断します。
また、ここで「2」と「3」の和である5も既知の素数としておきます。
※同様に「2」と「5」の和である「7」も既知の素数とすることができるのですが、
  既知の素数は最小にするというポリシーの元、既知であるのは「5」までとします。
  →変なこだわり。

次に4以上の偶数は全て最小公約数に2を持つ為、2で割り切れた時点で”素数でない”と判断し
試算の対象を奇数のみにします。
※故にFor文が3から始まって2Step(2ずつ増加)になっています。

しかし、これだけでは試算回数を約1/2程度にしただけに過ぎず、さほど計算回数を減らしたことに
なりません。ここで登場したのが平方根。つまりはです。

なぜ、平方根を使うと試算回数を減らすことができるのか?
がんばって説明します。※この証明を考えるのに手間取りました;

まず、素数判定する対象の値を n とします。
次に試算する値をA、割れた数をBとします。
そうすると次の式が成り立ちます。

n÷AB…余剰(0含む)

この式から余剰を除いて、式を変形させると次のようになります。
A×Bn

では、n=36としてABの組み合わせを考えてみましょう。
また、このときABの大小関係にも注目します。

A×B    ABの大小関係
1 ×36    A < B
2 ×18
3 ×12
4 × 9
6 × 6    A = B
9 × 4    A > B
12×3
18×2
36×1

こうやってみるとABは同じ数字の構成で、A = Bを中点として数字が入れ替わっているのがわかります。
また、A = Bとなったとき、ABの値がそれぞれ36の平方根である「6」であることがわかります。

このことから、A < B から A = Bまでの組み合わせで、A × Bnが成り立たなければ、 A > BでもA×Bnが成り立たないので、A < BからA = B( = の平方根)まで試算すればよい。
ということになるのです。

ここまで読んでくださった方には心から感謝申し上げます。

おわかりいただけたでしょうか…。
結構、頑張って書いてみましたが文書にするとどーも伝わりにくいような…。

Comment

素数判定を行うユーザー定義関数

対象:Excel2002, Excel2003, Excel2007, Excel2010 今年(2011年)に入ってから、「2011」が素数であることから、それに関連したツイートやブログ記事を見かける機会が何度かありました。 VBA(Visual Basic for Applications)でも、素数かどうかを判定するユーザー定義...
Trackback













管理者にだけ表示を許可する

Comment form

openclose

カテゴリ一覧

そま宗助

  • Author:そま宗助
  • タイ生まれのちょっと変な?日本人。
    農学博士の父とブラジル日系1世の母の間に生まれたため、普通の日本人とはちょっと違う視点で世界を見つめる男。

    最近、勉強会やカンファレンスにちょいちょい顔出ししてます。

    読書週間継続中?

    ストレングスファインダー
    1.収集心
    2.学習欲
    3.共感性
    4.指令性
    5.運命思考
プロフィール

※注意書き※
当ブログに掲載されているJavaScriptの動作確認はFirefoxでのみ行っております。他ブラウザでの動作に関しては保障できませんのでご注意ください。






1キロバイトの素材屋さん
フリーエリア
FC2カウンター

名前:
メール:
件名:
本文:

メールフォーム

Page Top

Powered by FC2 Blog |

FC2Ad

| Template Design by スタンダード・デザインラボ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。