0

素数などを見つけるクラスを作成するために、Javaで宿題を与えられました（コードでよくわかります）。

私のコード：

    class Primes {

    public static boolean IsPrime(long num) {
        if (num%2==0){
            return false;
        }

        for (int i=3; i*i<=num;i+=2) {
            if (num%i==0) {
                return false;    
            }
        }
        return true;
    }   //  End boolen IsPrime

    public static int[] primes(int min, int max){
        int counter=0;
        int arcount=0;

        for (int i=min;i<max;i++){
            if (IsPrime(i)){
                counter++;
            }   
        }

        int [] arr= new int[counter];
        for (int i=min;i<max;i++){
            if (IsPrime(i)){
                arr[arcount]=i;
                arcount++;
            }               
        }
        return arr;
    }   //  End Primes

    public static String tostring (int [] arr){
        String ans="";
        for (int i=0; i<arr.length;i++){
            ans= ans+arr[i]+ " ";
        }
        return ans;
    }

    public static int closestPrime(long num){
        long e = 0 , d = 0 , f = num;
        for (int i = 2; i <= num + 1 ; i++){
            if ((num + 1) % i == 0){
                if ((num + 1) % i == 0 && (num + 1) == i){
                    d = num + 1;
                    break;
                }
                num++;
                i = 1;
            }
        }
        num = f;
        for (int i = 2; i < num; i++){
            if ((num - 1) % i == 0){
                if ((num - 1) % i == 0 && (num - 1) == i){
                    e = num - 1;
                    break;
                }
                num--;
                i = 1;
            }
        }
        num = f;
        if (d - num < num - e) System.out.println("Closest Prime: "+d);
        else System.out.println("Closest Prime: "+e);

        return (int) num;
    }   //  End closestPrime

}//end class

私のコードの目標は、より速く（そして正しく）することです。私はこれを達成するのに苦労しています。提案？

**新しいコード：

class Primes {

     public static boolean IsPrime(int num) {

         if (num==1){
             return false;
         }
         for (int i=2; i<Math.sqrt(num);i++) {
             if (num%i==0) {
                 return false;
             }
         }
         return true;
     }
          //  End boolen IsPrime

     public static int[] primes(int min, int max){
         int size=0;
         int [] arrtemp= new int[max-min];

         for (int i=min;i<max;i++){
             if (IsPrime(i)){
                 arrtemp[size]=i;
                 size++;
             }   
         }

         int [] arr= new int[size];
         for (int i=0;i<size;i++){
                arr[i]=arrtemp[i];

             } 
         return arr;

     }  

    public static String tostring (int [] arr){
        String ans="";
        for (int i=0; i<arr.length;i++){
            ans= ans+arr[i]+ " ";
        }
        return ans;
    }

    public static int closestPrime(int num) {
        int count=1;    
        for (int i=num;;i++){

            int plus=num+count, minus=num-count;
            if (IsPrime(minus)){

                return minus;

            }

            if (IsPrime(plus)) {
                return plus;

            }
            count=count+1;
        }
    }   //  End closestPrime

}//end class

私はそれを少し良くしようとしました。あなたはどう思いますか、それはもっと改善することができますか？（速度テストはまだ高いです...）

4

3 に答える 3

1

あなたのprimes職務では：

  • 現在の数が2で割り切れるかどうかを確認します
  • それが素数であるかどうかを確認してください
  • 出力を入れる配列を作成します。
  • 配列に入れる前に、範囲内のすべての数値の素数性を再度確認してください。

問題は最後のステップにあります。各数値が素数であるかどうかを再確認することで、最もコストのかかる操作を複製しています。

動的データ構造を使用して、見つけた素数を追加することができます。そうすれば、一度だけチェックする必要があります。

または、入力範囲のサイズであるブール配列を作成することもできます。次に、素数を見つけたら、対応する配列値をtrueに設定します。

アップデート：

まだ多くの改善を行うことができますが、実装するために他の人よりも多くの作業を必要とするものもあります。テストの詳細を見て、ニーズに合うものを確認してください。

容易に解決できる問題：

  • 値を2回ループするのではなく、を使用しArrayListて、で見つけた素数を収集します。primes
  • ではclosestPrime、次のいずれかの側のすべての値をチェックしています。numこれらの半分は偶数であるため、素数ではありません。素数性について奇数のみをチェックするようにコードを適合させることができます。

実装が難しい：

何よりも、コードのボトルネックがどこにあるかを正確に把握するために時間を費やす必要があります。多くの場合、パフォーマンスの問題は、完全に問題ないと思われるコードが原因で発生します。開発環境で利用可能なコードプロファイリングオプションを検討することを検討してください。

于 2013-03-25T23:48:00.217 に答える
0

isPrime（）をかなりの数呼び出しますが、それぞれが非常に高価です。最初のステップは、それを行う回数を最小限に抑えることです。特定の番号で結果が変わらないため、2回以上呼び出す意味はありません。計算された値を保存することで、メモ化でこれを行うことができます。

ArrayList<Integer> memoList = new ArrayList<Integer>();
for(int i = 0; i < max; i++) {
  if(isPrime(i)) {
    memoList.add(i);
  }
}

これで、memoListは、最大で必要なすべての素数を保持し、max毎回再計算することなく、それらをすばやくループできます。

第二に、あなたはあなたの方法を改善することができますisPrime()。ソリューションは3からsqrt（n）までのすべての奇数をループしますが、素数がわかったので、素数をループするだけではどうでしょうか。

public static boolean IsPrime(long num) {
    for(int p : memoList) {
        if(num % p == 0) {
            return false;
        }
    }
    return true;
}

これらの変更により、コードの実行速度が劇的に向上するはずですが、素数を計算するさらに効率的な方法については多くの研究が行われています。素数に関するウィキペディアのページには、実験できるさらなる戦術（特に素数のふるい）に関する非常に優れた情報がいくつかあります。

これは宿題なので、提出するときは必ずこのページを引用する必要があります。このコードを使用して拡張することは大歓迎ですが、この質問や使用するその他のリソースを引用しないことは盗用です。

于 2013-03-25T23:45:39.430 に答える
0

あなたの答えにはいくつか問題があります。まず、2は素数です。IsPrimeの最初の条件はこれを破ります。第二に、素数法では、最小から最大まですべての数値を循環しています。すべての負の数とすべての偶数を安全に無視できます（IsPrimeの場合と同様）。これらの2つの方法を組み合わせて、余分なサイクルをすべて節約する方が理にかなっています。

于 2013-03-25T23:46:48.490 に答える