Java BigInteger 素数確認メソッドの処理について

自分が作った素数確認メソッドの処理問題があって、それを修正したいのだが・・・どこが問題起きてるのかわからない・・・よろしければ、訂正後のソース部分を載せてください。お願いします。

【詳細】
★入力を64ビット内の値は問題なく、それを超える値の場合、素数かどうかの(boolean)出力ができてない。
★問題発生した超える値の出力結果を何分待っても結果出ずに処理中のままになり、次への処理(System.out.prinln()など)に進まない。何度繰り返しても同じような事が起きる。
★ループはfor文で10進数の1で減少しつつ処理させているので、無限ループにはならない。
★符号なしです。

【素数確認メソッド】

lang
1import java.math.*;//BigIntegerインポート(取り込み)
2
3//素数確認
4public static boolean isSosuuNum(BigInteger x){
5	if(!x.mod(new BigInteger("2")).equals(BigInteger.ZERO)&&
6		!x.mod(new BigInteger("3")).equals(BigInteger.ZERO)&&
7		!x.mod(new BigInteger("5")).equals(BigInteger.ZERO)&&
8		!x.mod(new BigInteger("7")).equals(BigInteger.ZERO)&&
9		!x.equals(new BigInteger("1"))){
10		for(BigInteger bN = bigIntSqrt(x); bN.compareTo(BigInteger.ONE) > 0; bN = bN.subtract(BigInteger.ONE)){
11			if(x.mod(bN).equals(BigInteger.ZERO)) break; else if(bN.equals(new BigInteger("2"))) return true;
12		}
13	}else if(x.equals(new BigInteger("2")) || x.equals(new BigInteger("3")) ||
14			 x.equals(new BigInteger("5")) || x.equals(new BigInteger("7"))) return true;
15	return false;
16}

行動規範の内容に同意します

回答2件

ベストアンサー

素数判定は、アルゴリズムによっては速度に大きな差がでる可能性があります。
Integer での素数判定でアルゴリズムと動作を確認した上で、 BigIngeger 版に移すとよいです。
また、profile をつかって、どこで処理時間がかかっているかを調べるとよいとおもいます。

参考情報：

BigInteger prime testing http://codereview.stackexchange.com/questions/43490/
素数判定アルゴリズムの実行速度比較(Java) http://d.hatena.ne.jp/rockstar2007/20091105/1257422026

投稿2015/02/11 22:11

katoy

総合スコア22324

退会済みユーザー

2015/02/12 01:09

URL貼ってくれたBigInteger Prime testingサイトの公開ソースを応用し、内容を少し縮めさせたら、比較的にものすごく速く素数を見つけてくれるので、ベストアンサーとして選びました。64ビット～128ビットの素数を今まで数分から十数分だったのに、解決できたおかげで、数秒程度で確認可能になりました。ありがとうございます。【改良したソース】 import java.math.*;//BigIntegerインポート public static boolean isPrime(BigInteger x){ if((x.subtract(BigInteger.ONE)).nextProbablePrime().compareTo(x) == 0) return true; return false; }

退会済みユーザー

2015/02/12 04:18

BigInteger prime testingに公開されているソースって、もしかしたら素数かもしれないという出力ですね。（汗）何回か試したら素数のはずが素数として出力されてない時もあるし、素数ではないのに何故か素数として出力されてる・・・今、素数判定アルゴリズムの実行速度比較(Java)のソース3番目を応用し、素数を生成して、テキストに出力して、別のクラスで、素数かどうか確認したい値を作られた素数テキストファイルから比較して確認するというプログラムを作って処理速度試し中・・・

katoy

2015/02/12 15:31

いくつか興味ふかいソースコードをみつけたので紹介します。 - http://stefanreiser.de/eratosthenes/Eratosthenes.java - http://stackoverflow.com/questions/2385909/ - http://programmingpraxis.com/programming-with-prime-numbers-source-code-in-java/

退会済みユーザー

2015/02/12 16:03

何とか信頼のある素数をより早く割り出せるできるようになる方法ができました。方法は、gcd( (素数*素数), ((素数-1)*(素数-1)) ) = 1で確認すれば、上に書いた改良したソースで、より早く確実な素数を得れることできるようになりました。

退会済みユーザー

2015/02/12 16:08

ループはWhileループで繰り返し作業で確認取れるようにしております。素数は自動でランダムに1と0で入れてBigIntegerに入れてるので、ランダム素数ではなく普通に１つだけの素数を確認する場合なら改良したソースだけで十分です。ランダムで生成して素数かどうかの繰り返し作業で乱数素数確認する場合、上に説明したどおり＋改良したソースを応用すれば問題無いです。

退会済みユーザー

2015/02/12 16:17

ちなみに、上に書いた　gcd( (素数*素数), ((素数-1)*(素数-1)) ) = 1　の素数部分は全部一つ一つ違う値です。

退会済みユーザー

2015/02/12 16:27

【書き忘れの追記】 if条件で2,3,5,7のどれかと(素数-1)*(素数-1)をgcdで1とでたら素数になるので↓にも問題なく動くはずです。他の素数確認サイトで本当に素数かどうか試した。今だに問題無いです。 if(gcd( 2, ((素数-1)*(素数-1)) ) == 1 || gcd( 3, ((素数-1)*(素数-1)) ) == 1|| gcd( 5, ((素数-1)*(素数-1)) ) == 1 || gcd( 7, ((素数-1)*(素数-1)) ) == 1){ System.out.println("素数です。"); }else{ System.out.println(素数ではありません。); }

行動規範の内容に同意します

bigIntSqrtで時間がかかっているのではないでしょうか。bigIntSqrtの実装を教えてください。

（回答）

BigIntegerのインスタンスを取得する際に、new BigInteger(String)を使わずにBigInteger.valueOf(long)を使ったほうがパフォーマンスが良いです。また、何度も使う値は毎回newせずに、定数にしましょう。

それ以外にも、こんな感じでメソッドを作って置き換えると、コードの見通しが良くなります。

計算結果があっているかどうかは確認できていません。

lang
1// Java5以降
2
3import static java.math.BigInteger.*; // ZERO, ONE
4import java.math.BigInteger;
5import java.util.Arrays;
6import java.util.List;
7
8public final class App {
9
10    static final BigInteger TWO = BigInteger.valueOf(2);
11    static final BigInteger THREE = BigInteger.valueOf(3);
12    static final BigInteger FIVE = BigInteger.valueOf(5);
13    static final BigInteger SEVEN = BigInteger.valueOf(7);
14    static List<BigInteger> smallPrimeNumbers = Arrays.asList(TWO, THREE, FIVE, SEVEN);
15
16    public static boolean isSosuuNum(BigInteger x) {
17        if (isNotDivisible(x, TWO) && isNotDivisible(x, THREE) && isNotDivisible(x, FIVE) && isNotDivisible(x, SEVEN)
18            && x.equals(ONE)) {
19            for (BigInteger bN = bigIntSqrt(x); bN.compareTo(ONE) > 0; bN = bN.subtract(ONE)) {
20                if (isDivisible(x, bN)) {
21                    break;
22                }
23                else if (bN.equals(TWO)) {
24                    return true;
25                }
26            }
27        }
28        else if (smallPrimeNumbers.contains(x)) {
29            return true;
30        }
31        return false;
32    }
33
34    private static BigInteger bigIntSqrt(BigInteger x) {
35        BigInteger div = ZERO.setBit(x.bitLength() / 2);
36        BigInteger div2 = div;
37        for (;;) {
38            BigInteger y = div.add(x.divide(div)).shiftRight(1);
39            if (y.equals(div) || y.equals(div2)) {
40                return y;
41            }
42            div2 = div;
43            div = y;
44        }
45    }
46
47    static boolean isDivisible(BigInteger a, BigInteger b) {
48        return a.mod(b).equals(ZERO);
49    }
50
51    static boolean isNotDivisible(BigInteger a, BigInteger b) {
52        return !a.mod(b).equals(ZERO);
53    }
54
55}