3

以下の方法では、エラトステネスのふるい(包含除外アルゴリズム) を使用して、指定された数までの素数を生成していると思います。私が具体的に理解していないのは、(j/2)位置に設定されたビットをクリアする理由です。従う特定のルールはありますか？にはBitSet位置 x に設定されたビットが含まれており、この数値は素数または合成数です。だから、私は何が起こっているのかを追うことができません。

public static List<Integer> generatePrimes(int max) {
        BitSet primeSet = new BitSet(max / 2);
        primeSet.set(1, max / 2);
        int limit = (int) Math.sqrt(max);
        for (int i = 3; i <= limit; i += 2) {
            if (!primeSet.get(i / 2)) continue;
            for (int j = i * i; j < max; j += i * 2)
                primeSet.clear(j / 2);

        }

        List<Integer> listOfPrimes = new ArrayList<>();
        listOfPrimes.add(2);
        for (int i = primeSet.nextSetBit(0); i >= 0; i = primeSet.nextSetBit(i + 1)) {
            listOfPrimes.add(i * 2 + 1);
        }
        return listOfPrimes;
    }
4

4 に答える 4

2 
public static List<Integer> generatePrimes(int max) {

 BitSet primeSet = new BitSet(max / 2);  // host the numbers i up to max/2
 primeSet.set(1, max / 2);               // representing the odds (2i+1)
 int limit = (int) Math.sqrt(max);       //                      below max
 for (int i = 3; i <= limit; i += 2)        // enumerate odds in range 
 {                                          //       3 .. sqrt(max)
     if (!primeSet.get(i / 2)) continue;    // i=2k+1, i/2==(2k+1)/2== k
                                            // (here i is value, k is index)
     for (int j = i * i; j < max; j += i * 2)  // j=i*i is the first multiple
         primeSet.clear(j / 2);        // of i, where the marking off begins
 }                                     //  with step 2*i: 3: 9,6,15,21,...
                                       //                 7: 49,63,77,91,...
 List<Integer> listOfPrimes = new ArrayList<>();
 listOfPrimes.add(2);                     // 2 is known to be prime a priori
 for (int i = primeSet.nextSetBit(0);     // starting with first set bit in
                                          //                 BitSet primeSet,
          i >= 0;                         // 1: until the end of primeSet  
          i = primeSet.nextSetBit(i + 1)  // 3: and go to next set bit
          ) {
     listOfPrimes.add(i * 2 + 1);         // 2: add 2i+1 to the list of primes,
 }                                        // (here i is index)
 return listOfPrimes;
}

ふるいの一部として、1772 年にサミュエル・ホースリー FRS 牧師が知っていたように、9 から始まるオッズの 3 番目の数字と、一般にn 2から始まるn番目の数字をマークする必要があります。

リストに沿って数えるだけでは非効率的です。ふるいの効率の鍵は、アドレスによるメモリへの直接アクセスです。ここでの数値の配列内の数値のアドレスは、数値の値そのものです (この値とアドレスの融合は、さまざまな整数ソート方法の効率の鍵でもあります)。

3 番目の奇数を直接計算するには、前の奇数に 6 を加算して次の奇数を取得する必要があります。5 番目ごとに 10 を追加し、1i番目ごとに – 2*i.

ちなみに、このコードは少し改善することができます。それらの間の距離にある数値の場合2*i、セット内のインデックスは の距離にありiます。常に 2 ずつ削除する必要はありません。開始インデックスを計算して だけインクリメントするだけiです。

編集: そのコードは次の疑似コードと同等です:

defn primes(max):
  sieve := makeArray(3,5,7 ... max, True)
  for p from 3 to sqrt(max) step 2:
    if sieve[p]:
        for i from p * p to max step 2*p:
            sieve[i] := False
  primes = {2} + {all i in (3,5,7, ... max) such that sieve[i] is True}
于 2013-05-11T14:56:18.533 に答える
1

プライムセットのビットは、数値 2x+1 を表します。ここで、x はビットセットのインデックスです。したがって、プライムセットに {1, 2, 3, 5, 6, 8, 9, 11, 14} が含まれている場合、それらは数値 {3, 5, 7, 11, 13, 17, 19, 23, 29} を表します。

素数を使ったプログラミングに興味がある場合は、私のブログでこのエッセイをお勧めします。とりわけ、エラトステネスのふるいと、あなたを悲しませている計算について説明します。

編集：コメントで説明されているように、エラトステネスの単純なふるいを追加します。

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            output p
            for i from p * p to n step p
                sieve[i] := False
于 2013-05-11T12:35:48.160 に答える