22

注:以下のバージョン 2 では、エラトステネスのふるいを使用しています。私が最初に尋ねたことに役立ついくつかの回答があります。エラトステネスの篩法を選択して実装し、質問のタイトルとタグを適切に変更しました。助けてくれたみんなに感謝します！

序章

指定された上限よりも小さい素数を含む int の配列を生成する、この手の込んだ小さなメソッドを作成しました。とてもよく効きますが、気になることがあります。

メソッド

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    int [] primes = new int [index];
    while(--index >= 0) {
        primes [index] = temp [index];
    }
    return primes;
}

私の懸念

私の懸念は、メソッドが返す要素の最終的な数に対して大きすぎる配列を作成していることです。問題は、指定された数よりも小さい素数の数を正しく推測する良い方法がわからないことです。

集中

これは、プログラムが配列を使用する方法です。これは私が改善したいものです。

  1. 制限未満のすべての数値を保持するのに十分な大きさの一時配列を作成します。
  2. 生成した数を数えながら、素数を生成します。
  3. 素数だけを保持するのに適切な次元の新しい配列を作成します。
  4. 巨大な配列から各素数を正しい次元の配列にコピーします。
  5. 生成した素数だけを保持する正しい次元の配列を返します。

質問

  1. 両方の配列を反復処理して要素を 1 つずつコピーすることなく、temp[]ゼロ以外の要素を持つチャンク全体を (一度に) コピーできます か?primes[]
  2. インスタンス化時に次元を要求するのではなく、要素が追加されるにつれて成長できるプリミティブの配列のように動作するデータ構造はありますか? プリミティブの配列を使用する場合と比較して、パフォーマンスはどの程度低下しますか?

バージョン 2 ( Jon Skeetに感謝):

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    return Arrays.copyOfRange(temp, 0, index);
}

エラストステネスのふるいを使用するバージョン 3 ( Paul Tomblinに感謝) :

private static int [] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    for (int i = 2; i * i <= max; i++) {
        if (!isComposite [i]) {
            for (int j = i; i * j <= max; j++) {
                isComposite [i*j] = true;
            }
        }
    }
    int numPrimes = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) numPrimes++;
    }
    int [] primes = new int [numPrimes];
    int index = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) primes [index++] = i;
    }
    return primes;
}
4

13 に答える 13

13

配列のすべての要素をすべての可能な要素と比較して素数を見つける方法は、非常に非効率的です。一度にアレイ全体でエラトステネスのふるいを行うことで、大幅に改善できます。はるかに少ない比較を行うだけでなく、除算ではなく加算も使用します。分割はずっと遅いです。

于 2009-02-25T14:57:58.907 に答える
10

ArrayList<>エラトステネスのふるい

// Return primes less than limit
static ArrayList<Integer> generatePrimes(int limit) {
    final int numPrimes = countPrimesUpperBound(limit);
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    boolean [] isComposite    = new boolean [limit];   // all false
    final int sqrtLimit       = (int)Math.sqrt(limit); // floor
    for (int i = 2; i <= sqrtLimit; i++) {
        if (!isComposite [i]) {
            primes.add(i);
            for (int j = i*i; j < limit; j += i) // `j+=i` can overflow
                isComposite [j] = true;
        }
    }
    for (int i = sqrtLimit + 1; i < limit; i++)
        if (!isComposite [i])
            primes.add(i);
    return primes;
}

以下の素数の上限の式max( wolfram.comを参照):

static int countPrimesUpperBound(int max) {
    return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0;
}
于 2009-02-26T02:22:31.147 に答える
8

を作成し、最後ArrayList<Integer>に に変換しint[]ます。

さまざまなサードパーティIntList(など) のクラスがありますが、いくつかの整数をボックス化することの影響を本当に心配していない限り、私はそれについて心配しません。

Arrays.copyOfただし、新しい配列を作成するために使用できます。必要に応じてサイズを 2 倍にしてサイズを変更し、最後にトリミングすることもできます。それは基本的にArrayList動作を模倣することになります。

于 2009-02-25T14:58:52.100 に答える
7

エラトステネスの篩を使用したアルゴリズム

public static List<Integer> findPrimes(int limit) {

    List<Integer> list = new ArrayList<>();

    boolean [] isComposite = new boolean [limit + 1]; // limit + 1 because we won't use '0'th index of the array
    isComposite[1] = true;

    // Mark all composite numbers
    for (int i = 2; i <= limit; i++) {
        if (!isComposite[i]) {
            // 'i' is a prime number
            list.add(i);
            int multiple = 2;
            while (i * multiple <= limit) {
                isComposite [i * multiple] = true;
                multiple++;
            }
        }
    }

    return list;
}

上記のアルゴを描いた画像（灰色のセルは素数を表します。最初はすべての数を素数と見なしているため、グリッド全体が最初は灰色です。）

ここに画像の説明を入力

画像ソース:ウィキメディア

于 2013-12-22T13:57:48.740 に答える
2

最も簡単な解決策は、配列の代わりにCollections Frameworkのメンバーを返すことです。

于 2009-02-25T14:58:38.827 に答える
2

Java 1.5 を使用していますか? 返品List<Integer>して使用してみませんArrayList<Integer>か？を返す必要がある場合は、処理の最後にint[]List を に変換することで実行できます。int[]

于 2009-02-25T15:00:54.983 に答える
1

Paul Tomblin が指摘しているように、より優れたアルゴリズムがあります。

しかし、あなたが持っているものを維持し、結果ごとのオブジェクトが大きすぎると仮定します:

配列に追加するだけです。そのため、比較的小さな int[] 配列を使用してください。完全に使用されたら、それをリストに追加して、置換を作成します。最後に、正しいサイズの配列にコピーします。

または、int[] 配列のサイズを推測します。小さすぎる場合は、現在の配列サイズよりも少し大きいサイズの int[] に置き換えます。このパフォーマンスのオーバーヘッドは、サイズに比例したままです。(これについては、最近の stackoverflow ポッドキャストで簡単に説明しました。)

于 2009-02-25T15:06:22.910 に答える
1

基本的なふるいができたので、内側のループは まで続けるだけでよいことに注意してくださいtemp[i]*temp[i] > prime。

于 2009-02-25T15:13:05.953 に答える
1

私は本当に効率的な実装をしています:

  1. 偶数を保持しないため、メモリ使用量が半分になります。
  2. を使用しBitSet、数値ごとに 1 ビットのみを必要とします。
  3. 間隔の素数の上限を推定するinitialCapacityため、配列の を適切に設定できます。
  4. ループ内でいかなる種類の除算も実行しません。

コードは次のとおりです。

public ArrayList<Integer> sieve(int n) {
    int upperBound = (int) (1.25506 * n / Math.log(n));
    ArrayList<Integer> result = new ArrayList<Integer>(upperBound);
    if (n >= 2)
        result.add(2);

    int size = (n - 1) / 2;
    BitSet bs = new BitSet(size);

    int i = 0;
    while (i < size) {
        int p = 3 + 2 * i;
        result.add(p);

        for (int j = i + p; j < size; j += p)
            bs.set(j);

        i = bs.nextClearBit(i + 1);
    }

    return result;
}
于 2015-03-01T12:16:32.630 に答える
0

コードを再構築します。一時配列を破棄し、代わりに整数を素数テストするだけの関数を記述します。ネイティブ型のみを使用しているため、かなり高速です。次に、たとえば、素数である整数のリストをループして作成してから、最終的にそれを配列に変換して返すことができます。

于 2009-02-25T15:00:20.240 に答える