-6

1000000 番目のプリミティブ数を 10 分以内に決定するコードが必要です。以下のクラスを作成しましたが、必要なほど高速ではありません。このクラスを最適化して計算速度を改善するにはどうすればよいですか? を呼び出すことで、このクラスを使用できますget_thPrimitive(int number)。それは長い時間を返します。

public class PrimitiveF
{
    // this is our class named PrimitiveF
    private static boolean isPrimitive(long n) 
    {
        //isPrimitive method is a private static method that is used in get_thPrimitive method
        //this method tells us if the number is primitive or not 
        long p=(long)Math.sqrt(n);//here we get square of the input number

        int i=2;
        while(i<=p)//now we check the nember is primitive or not if it is primitive we'll return true
        {
            int k=0;
            for(int j=2;j<=i;j++)
                if(i%j==0)
                    k++;
            if(k==1)
            {
                if(n%i == 0)
                    return false;
            }
            i++;
        }

        return true;
    }

    public static long get_thPrimitive(int n)//get_thPrimitive method is a public static //method
    {
        //this method would give us the Xth primitive number
        int count=0,i=2;
        while(count < n)
        {
            if(isPrimitive(i))
                count++;
            i++;
        }

        return --i;
    }
}
4

2 に答える 2

2

プリミティブとは素数を意味する場合 (用語が同じ意味で使用されているのを見てきました)、最も遅いアルゴリズムの 1 つを使用しています。はるかに高速なソリューションについては、「ふるい」、おそらく「二次ふるい」を検索してください。

編集：ああ、ふるいのために、サイズ16,000,000の配列が必要です（100万番目の素数は15.5Mに少し恥ずかしがり屋です）。

于 2013-11-02T10:40:47.867 に答える
2

n に素約数がない場合にのみ、その isPrimitive() メソッドから false を返します。それを行うには、sqrt(n) までのすべての素数を生成します...しかし、1 つだけ大きなものを実行するためだけに多くの内部素数テストを使用しており、それらの内部素数テストに遅いメソッドを使用しています。

コードが正しいが遅すぎる場合は、次の方法で大幅な高速化を実現できます。

  1. n が偶数の場合、n が 2 の場合は true を返し、それ以外の偶数の場合は false を返します。
  2. ループ内で、3 から始まり sqrt(n)+1 以下の奇数除数のみをテストします。これらが素約数であるかどうかは気にしないでください。それは問題ではなく、素数の除数をテストしても速度が低下するだけです。

n が奇数で、上記で検出された奇数の約数がない場合、それは素数です。

これにより、コードが大幅に高速化されます。それでも十分に高速でない場合は、Sieve アルゴリズムを使用して調査できます。基本的な方法は古代のエラトステネスによるもので、ウィキペディアに記載されています

于 2013-11-02T10:34:18.123 に答える