2008年10月02日

メルセンヌ素数を求めるjavaプログラム

GIMPSにより最大の素数が更新されたニュースを見ました。
1000万桁を超えるメルセンヌ素数で2^n -1で表わされ、nも素数になります。

javaには多倍長計算用にBigDecimalが用意されていると言うことなので、エラトステネスの篩で素数を求めて、メルセンヌ素数になるかどうか判定するプログラムを作ってみました。
nは10000までの制限もありますが、まったく最適化に向かないコードで、かなり遅いです。

最初J#で書き始めましたがMSはBigDecimalを実装してないので、あらためてeclipse(windows版)のインストールから始めましたが、5時間で18番目のメルセンヌ素数が出てきました。

//実行結果(実行中)
メルセンヌ素数を探します。
0:2:55: 2^3-1 = 7
0:2:55: 2^5-1 = 31
0:2:55: 2^7-1 = 127
0:2:55: 2^13-1 = 8191
0:2:55: 2^17-1 = 131071
0:2:55: 2^19-1 = 524287
0:2:55: 2^31-1 = 2147483647
0:2:55: 2^61-1 = 2305843009213693951
0:2:55: 2^89-1 = 618970019642690137449562111
0:2:55: 2^107-1 = 162259276829213363391578010288127
0:2:55: 2^127-1 = 170141183460469231731687303715884105727
0:3:10: 2^521-1 = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
0:3:22: 2^607-1 = 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127
0:11:44: 2^1279-1 = 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
1:12:32: 2^2203-1 = 1475979915214180235084898622737381736312066145333169775147771216478570297878078949377407337049389289382748507531496480477281264838760259191814463365330269540496961201113430156902396093989090226259326935025281409614983499388222831448598601834318536230923772641390209490231836446899608210795482963763094236630945410832793769905399982457186322944729636418890623372171723742105636440368218459649632948538696905872650486914434637457507280441823676813517852099348660847172579408422316678097670224011990280170474894487426924742108823536808485072502240519452587542875349976558572670229633962575212637477897785501552646522609988869914013540483809865681250419497686697771007
1:23:45: 2^2281-1 = 446087557183758429571151706402101809886208632412859901111991219963404685792820473369112545269003989026153245931124316702395758705693679364790903497461147071065254193353938124978226307947312410798874869040070279328428810311754844108094878252494866760969586998128982645877596028979171536962503068429617331702184750324583009171832104916050157628886606372145501702225925125224076829605427173573964812995250569412480720738476855293681666712844831190877620606786663862190240118570736831901886479225810414714078935386562497968178729127629594924411960961386713946279899275006954917139758796061223803393537381034666494402951052059047968693255388647930440925104186817009640171764133172418132836351
5:2:38: 2^3217-1 = 259117086013202627776246767922441530941818887553125427303974923161874019266586362086201209516800483406550695241733194177441689509238807017410377709597512042313066624082916353517952311186154862265604547691127595848775610568757931191017711408826252153849035830401185072116424747461823031471398340229288074545677907941037288235820705892351068433882986888616658650280927692080339605869308790500409503709875902119018371991620994002568935113136548829739112656797303241986517250116412703509705427773477972349821676443446668383119322540099648994051790241624056519054483690809616061625743042361721863339415852426431208737266591962061753535748892894599629195183082621860853400937932839420261866586142503251450773096274235376822938649407127700846077124211823080804139298087057504713825264571448379371125032081826126566649084251699453951887789613650248405739378594599444335231188280123660406262468609212150349937584782292237144339628858485938215738821232393687046160677362909315071


//2008/10/1 少し判り易く修正
//さらに改修
//テストプログラム
import java.io.*;
import java.math.*;
import java.util.*;

//メルセンヌ素数をLucas-Lehmerテストによって確認するクラス
public class Mersenne {
static BigDecimal number2 = new BigDecimal(2);

static BigDecimal number1 = new BigDecimal(1);

static BigDecimal zero = new BigDecimal(0);

// Lucas-Lehmerテストによって素数を判別する
public static boolean IsMersenne(int sosu) {
BigDecimal worknumber = new BigDecimal(4);
BigDecimal merse = new BigDecimal(2);
BigDecimal result[] = new BigDecimal[2];
int i;
for(i=1; i merse = merse.multiply(number2);
}
merse = merse.subtract(number1);

for (i = 2; i < sosu; i++) {
worknumber = worknumber.multiply(worknumber);
worknumber = worknumber.subtract(number2);
result = worknumber.divideAndRemainder(merse);
worknumber = result[1];
}
result = worknumber.divideAndRemainder(merse);
if (result[1].compareTo((zero)) == 0) {
Calendar cal = Calendar.getInstance();
int hour = cal.get(Calendar.HOUR_OF_DAY);
int minu = cal.get(Calendar.MINUTE);
int sec = cal.get(Calendar.SECOND);
System.out.println(hour + ":" + minu + ":" + sec + ": 2^" + sosu
+ "-1 = " + merse);
return true;
}
return false;
}

/**
* @param args
*/
public static void main(String[] args) {
long time = System.currentTimeMillis();

System.out.println("メルセンヌ素数を探します。");
// エストラネスの篩を使ってmaxnumberまでの素数を探す
int maxnumber = 10000;
byte sosu[] = new byte[maxnumber];
for (int i = 2; i < maxnumber; i++) {
if (sosu[i] != 0) {
// 合成数
continue;
}
//素数なのでメルセンヌ素数になるかチェックする
if (IsMersenne(i)) {
}
//合成数を篩にかける
int j = i * 2;
while (j < maxnumber) {
sosu[j] = 1;
j = j + i;
}
}
System.out.println("総実行時間:" + (System.currentTimeMillis() - time)
+ "msec");
}
}


トラックバックURL

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔