エラトステネスの篩で素数を見つける (原文:この配列を準備するより良い方法はありますか?)

https://stackoverflow.com/questions/586284

06-09-2019
|

質問

注記： 以下のバージョン 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;
}

私の懸念

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

集中

これは、プログラムが配列を使用する方法です。これは改善していきたいところです。

すべての数値を制限よりも少ない保持するのに十分な大きさの一時的な配列を作成します。
生成した数のカウントを維持しながら、私は素数を生成します。
プライムナンバーだけを保持するための適切な次元である新しい配列を作成します。
各プライム番号を巨大な配列から正しいディメンションの配列にコピーします。
生成した素数だけを保持する正しい次元の配列を返します。

質問

チャンク全体を (一度に) コピーできますか?temp[] それにはゼロ以外の要素があります primes[]両方の配列を繰り返して、要素を1つずつコピーする必要がありませんか？
インスタンス化時に寸法を必要とするのではなく、要素が追加されるにつれて成長できる一連のプリミティブのように振る舞うデータ構造はありますか？一連のプリミティブを使用することと比較したパフォーマンスペナルティは何ですか？

バージョン 2 (おかげでジョン・スキート):

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 (おかげでポール・トンブリン) を使用します。エラストステネスのふるい:

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;
}

解決

すべての可能な因子とアレイのすべての単一の要素を比較することにより、素数を見つけることのあなたの方法は、恐ろしく非効率的です。一度にアレイ全体エラトステネスするのふるいを行うことによって、非常にそれを改善することができます。はるかに少ない比較を行うだけでなく、それはまた、分裂ではなく、追加を使用しています。部門は道遅くなります。

他のヒント

`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;
}

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

さまざまなサードパーティ製のIntList（など）の周りのクラスがありますが、あなたは、の本当にのいくつかの整数をボクシングのヒット心配している場合を除き、私はそれについて心配しないでしょう。

あなたはしかし、新しい配列を作成するためにArrays.copyOfを使用することができます。また、サイズが必要に毎回倍増してサイズを変更した後、最後にトリミングしたい場合があります。それは基本的にArrayListの挙動を模倣することでしょう。

エラトステネスのふるいを使用してアルゴ

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;
}

上記アルゴを示す画像（グレーカラーセルは素数を表す。我々はintially素数としてすべての数値を考慮しているので、全体のグリッドでは、最初は灰色である。）

ここに画像の説明を入力します

イメージソース：ウィキメディアの

最も簡単な解決策は、 Collections Frameworkの一部のメンバーを返すようになりますの代わりにアレイの

は、Java 1.5を使用していますか？なぜList<Integer>を返すとArrayList<Integer>を使わないのでしょうか？あなたがint[]を返す必要がない場合は、処理の最後にint[]するリストを変換することによってそれを行うことができます。

ポールTomblinが指摘するように、より良いアルゴリズムがあります。

しかし、あなたが持っているものと調和し、その結果につきオブジェクトと仮定すると大きすぎるます：

あなたは今まで、アレイに追加されます。だから、比較的小規模のint []配列を使用しています。それはフルだときに使用することは、リストに追加し、交換を作成します。終わりに、正しいサイズの配列にコピーします。

あるいは、INT []配列のサイズを推測します。それが小さすぎると、現在の配列のサイズよりも大きいサイズ分数で[] int型で置き換えます。このパフォーマンスのオーバーヘッドはサイズに比例ままになります。（これは、最近のstackoverflowのポッドキャストで簡単に説明しました。）

は、今、あなたは代わりに基本的なふるいを持っていることを、内側のループのみtemp[i]*temp[i] > primeまで続ける必要があることに注意してください。

本当に効率的な実装があります。

偶数を保持しないので、メモリ使用量が半分になります。
を使用しております BitSet, 、数値ごとに 1 ビットだけが必要です。
区間上の素数の数の上限を推定するので、次のように設定できます。 initialCapacity 配列に適切に対応します。
ループ内ではいかなる種類の除算も実行しません。

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

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;
}

あなたのコードを再構築。一時的な配列を捨て、代わりにちょうど整数をプライムテストする関数を書きます。あなたが唯一のネイティブ型を使用しているので、それは、適度に高速になります。その後することができます、例えば、ループのため、最終的に返すために、配列にそれを変換する前に、首相は整数のリストを作成します。

私は最終的にプログラムを終了しましたこれは、最適化されたふるいです。

public static int[] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    LinkedList<Integer> Primes = new LinkedList<>(); //linkedlist so not have to iterate 2 times
    int sqrt = (int) Math.sqrt(max); //end at the square root
    for (int i = 2; i <= sqrt; i++) {
        if (!isComposite[i]) {
            int s = i*i; //start from the prime's square
            while (s <= max) {
                isComposite[s] = true; //oh no its a not prime
                s+=i;
            }
        }
    }
    for(int i = 2; i < max; i++){
        if(!isComposite[i]){
            Primes.add(i);
        }
    }
    int[] result = new int[Primes.size()];
    for (int i = 0; i < result.length; i++) {
        result[i] = Primes.get(i);
    }
    return result;
}

これはあなたの状況を、スイートなりますが、あなたは私のアプローチを見てみることができるかどうかわかりません。私は、エラトステネスするのふるいを使用して地雷を使用します。

  public static List<Integer> sieves(int n) {
        Map<Integer,Boolean> numbers = new LinkedHashMap<>();

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

        //First generate a list of integers from 2 to 30
        for(int i=2; i<n;i++){
            numbers.put(i,true);
        }

        for(int i : numbers.keySet()){
            /**
             * The first number in the list is 2; cross out every 2nd number in the list after 2 by 
             * counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):
             * 
             * The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by 
             * counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):
             * The next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every
             * 7th number in the list after 7, but they are all already crossed out at this point,
             * as these numbers (14, 21, 28) are also multiples of smaller primes because 7 × 7 is greater than 30. 
             * The numbers not crossed out at this point in the list are all the prime numbers below 30:
             */
            if(numbers.get(i)){
                for(int j = i+i; j<n; j+=i) {
                    numbers.put(j,false);
                }
            }
        }


        for(int i : numbers.keySet()){
            for(int j = i+i; j<n && numbers.get(i); j+=i) {
                numbers.put(j,false);
            }
        }

        for(int i : numbers.keySet()){
           if(numbers.get(i)) {
               primes.add(i);
           }
        }
        return primes;
    }

ウィキペディアに図示された各ステップのための追加されたコメント

私はHashMapを使用して行われ、それは非常に単純な発見した。

import java.util.HashMap;
import java.util.Map;

/*Using Algorithms such as sieve of Eratosthanas */

public class PrimeNumber {

    public static void main(String[] args) {

        int prime = 15;
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

        hashMap.put(0, 0);
        hashMap.put(1, 0);
        for (int i = 2; i <= prime; i++) {

            hashMap.put(i, 1);// Assuming all numbers are prime
        }

        printPrimeNumberEratoshanas(hashMap, prime);

    }

    private static void printPrimeNumberEratoshanas(HashMap<Integer, Integer> hashMap, int prime) {

        System.out.println("Printing prime numbers upto" + prime + ".....");
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            if (entry.getValue().equals(1)) {
                System.out.println(entry.getKey());
                for (int j = entry.getKey(); j < prime; j++) {
                    for (int k = j; k * j <= prime; k++) {
                        hashMap.put(j * k, 0);
                    }
                }

            }
        }

    }

}

これが効果的であると考えて

public static void primes(int n) {
        boolean[] lista = new boolean[n+1];
        for (int i=2;i<lista.length;i++) {
            if (lista[i]==false) {
                System.out.print(i + " ");
            }
            for (int j=i+i;j<lista.length;j+=i) {
                lista[j]=true;
            }
        }
    }

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

エラトステネスの篩で素数を見つける (原文:この配列を準備するより良い方法はありますか?)

導入

方法

私の懸念

集中

質問

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

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