質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.47%

  • Java

    14101questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

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

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 1,503
退会済みユーザー

退会済みユーザー

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

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

【素数確認メソッド】
import java.math.*;//BigIntegerインポート(取り込み)

//素数確認
public static boolean isSosuuNum(BigInteger x){
    if(!x.mod(new BigInteger("2")).equals(BigInteger.ZERO)&&
        !x.mod(new BigInteger("3")).equals(BigInteger.ZERO)&&
        !x.mod(new BigInteger("5")).equals(BigInteger.ZERO)&&
        !x.mod(new BigInteger("7")).equals(BigInteger.ZERO)&&
        !x.equals(new BigInteger("1"))){
        for(BigInteger bN = bigIntSqrt(x); bN.compareTo(BigInteger.ONE) > 0; bN = bN.subtract(BigInteger.ONE)){
            if(x.mod(bN).equals(BigInteger.ZERO)) break; else if(bN.equals(new BigInteger("2"))) return true;
        }
    }else if(x.equals(new BigInteger("2")) || x.equals(new BigInteger("3")) ||
             x.equals(new BigInteger("5")) || x.equals(new BigInteger("7"))) return true;
    return false;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/02/12 10: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 13:18

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

    キャンセル

  • 2015/02/13 00: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/13 01:03

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

    キャンセル

  • 2015/02/13 01:08

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

    キャンセル

  • 2015/02/13 01:17

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

    キャンセル

  • 2015/02/13 01: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(素数ではありません。);
    }

    キャンセル

+1

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


(回答)

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

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

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

// Java5以降

import static java.math.BigInteger.*; // ZERO, ONE
import java.math.BigInteger;
import java.util.Arrays;
import java.util.List;

public final class App {

    static final BigInteger TWO = BigInteger.valueOf(2);
    static final BigInteger THREE = BigInteger.valueOf(3);
    static final BigInteger FIVE = BigInteger.valueOf(5);
    static final BigInteger SEVEN = BigInteger.valueOf(7);
    static List<BigInteger> smallPrimeNumbers = Arrays.asList(TWO, THREE, FIVE, SEVEN);

    public static boolean isSosuuNum(BigInteger x) {
        if (isNotDivisible(x, TWO) && isNotDivisible(x, THREE) && isNotDivisible(x, FIVE) && isNotDivisible(x, SEVEN)
            && x.equals(ONE)) {
            for (BigInteger bN = bigIntSqrt(x); bN.compareTo(ONE) > 0; bN = bN.subtract(ONE)) {
                if (isDivisible(x, bN)) {
                    break;
                }
                else if (bN.equals(TWO)) {
                    return true;
                }
            }
        }
        else if (smallPrimeNumbers.contains(x)) {
            return true;
        }
        return false;
    }

    private static BigInteger bigIntSqrt(BigInteger x) {
        BigInteger div = ZERO.setBit(x.bitLength() / 2);
        BigInteger div2 = div;
        for (;;) {
            BigInteger y = div.add(x.divide(div)).shiftRight(1);
            if (y.equals(div) || y.equals(div2)) {
                return y;
            }
            div2 = div;
            div = y;
        }
    }

    static boolean isDivisible(BigInteger a, BigInteger b) {
        return a.mod(b).equals(ZERO);
    }

    static boolean isNotDivisible(BigInteger a, BigInteger b) {
        return !a.mod(b).equals(ZERO);
    }

}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/02/10 13:21

    質問追記にbigIntSqrtメソッドを載せておきました。

    キャンセル

  • 2015/02/12 10:04

    なるほど、同じ値でメンバ変数をよく使うのであればfinalで固定と、できるだけnewを使わないほうがいいのかー・・・_〆(0∀0 )メモメモ

    キャンセル

  • 2015/02/12 13:38

    念のため。
    BigIntegerは「イミュータブル」なので定数(static final)にしても問題ありませんが、イミュータブルでない場合は注意が必要です。

    キャンセル

  • 2015/02/13 01:05

    fmfm・・・イミュータブルってなんだろう???ぐぐって調べるわb
    注意書きありがとうございます。

    キャンセル

関連した質問

  • 解決済

    電卓プログラムの質問です

    javaにて電卓を作成しています。 以下が作成中のコードです。状態としては、コンソールに表示される段階のコードになります。 import java.io.BufferedRead

  • 解決済

    プログラムについての質問です

    javaにて、プログラムを作成しています。 以下がソースになります。コンパイルと実行が出来る状態です。 流れとして、まずは > のみが表示され、「入力された文字の末尾が"ん"で

  • 受付中

    [java][日付チェック]質問

    java初心者です。 テキストファイルを一行づつ読み込んで行く時に、 32日や14月など、異常な日付が紛れていた場合例外として処理する方法はありますでしょうか? while ((

  • 解決済

    Javaの条件判断の書き方

    javaにおいて、ある数字(0から9まで)を設定した後にキーボードから値を入力(0から9まで)し、設定した正解とあっていれば正解、そうでなければ大きいか小さいかを表示し、4回繰り返

  • 受付中

    このコードをスマートにしてください

    aをb乗するプログラムを作成しております。 前回の質問で回答していただいた方々のおかげでとりあえずやりたかった動作をしてくれるプログラムは完成しました。 しかしこのプログラムを

  • 受付中

    配列について

    例えば boolean A[] = new boolean[]{false, true, false}; のような配列があったとして 配列Aが全てtrueの場合Bという処理を

  • 解決済

    クラスリストの比較でcontainsが動作してくれない

    containsを用いて2つのクラスリストを比較したいのですが、うまく動作してくれません。 class Order{ public int id; publi

  • 解決済

    Javaの抽象クラスに抽象フィールドを持たせる方法

    私は数学関係のプログラムを作っていて、その中で体を表現するための抽象クラスを作ったのですが、0と1の存在をどのように表せばよいかわかりません。 具体的には、下のコードのzero()

同じタグがついた質問を見る

  • Java

    14101questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。