1

n(エラトステネスのふるい)までの素数を見つける方法を書いています。はい、これは宿題です。私が書いた方法でパフォーマンスを改善しようとしています。ここ数日間、これを微調整してきましたが、与えられた疑似コードに従ってパフォーマンスを向上させることができません。

疑似コードは次のとおりです:
処理する数値のキューを作成
します 2 から n までの整数でキューを埋めます
素数を格納する空の結果キューを作成します
次の手順を繰り返します:
数値のキューから最初の値を削除して、次の素数 p を取得します
p を素数の結果キューに入れる p
で割り切れるすべての数を削除する数のキューをループします
(p は n の平方根より小さい)
残りの値はすべて素数であるため、素数の結果キューに転送します

これが私の現在の方法です：

 public static Queue<Integer> getPrimes(int n) throws IllegalArgumentException
{
    if (n<2)
    {
        throw new IllegalArgumentException();
    }

    Queue<Integer> integers = new LinkedList<Integer>();
    Queue<Integer> primes = new LinkedList<Integer>();
    for (int i = 2; i <= n ; i++) {
        integers.add(i);
    }
    boolean[] isMultiple = new boolean[n + 1];

    for(int iterate = integers.remove(); iterate <= n; iterate++)
    {

        if(!isMultiple[iterate])
        {
            primes.add(iterate);
            for(int multiples = iterate * iterate; multiples >= 0 && multiples <= n; multiples += iterate)
            {
                isMultiple[multiples] = true;
            }
        }
    }
    return primes;
}
4

2 に答える 2

0

最初の小さなステップとして、キューを削除して共通ループintegersに置き換えることができます。for

for (int iterate = 2; iterate < n; iterate++)
{
     if (!isMultiple[iterate]) 
     {
         ...
     }
}
于 2015-02-25T19:13:08.520 に答える