20

3 を超えるすべての素数は、次を使用して生成できることがわかっています。

6 * k + 1
6 * k - 1

ただし、上記の式から生成されるすべての数値は素数ではありません。

For Example:    
6 * 6 - 1 = 35 which is clearly divisible by 5.

このような状態を解消するために、ふるい法を用いて、上記の式から発生する数の因数となる数を取り除きました。

事実を使用して：

素因数がない数は、素数であると言われます。

  1. 上記の式を使用してすべての素数を生成できるためです。
  2. 上記の数の倍数をすべて削除できれば、素数だけが残ります。

1000 未満の素数を生成します。

ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
int n = 1000;
for (int i = 1; i <= (n / 6) ; i++) {
//get all the numbers which can be generated by the formula
    int prod6k = 6 * i;
    primes.add(prod6k - 1);
    primes.add(prod6k + 1);
}
for (int i = 0; i < primes.size(); i++) {
    int k = primes.get(i);
    //remove all the factors of the numbers generated by the formula
    for(int j = k * k; j <= n; j += k)//changed to k * k from 2 * k, Thanks to DTing
    {           
        int index = primes.indexOf(j); 
        if(index != -1)
            primes.remove(index);
    }
}
System.out.println(primes);

ただし、この方法では正しく素数が生成されます。これは、Sieve でチェックするすべての数値をチェックする必要がないため、はるかに高速に実行されます。

私の質問は、エッジケースが欠けているということですか? これははるかに優れていますが、これを使用している人を見たことがありません。私は何か間違ったことをしていますか？

このアプローチをさらに最適化できますか?

boolean[]an の代わりにaを使用するArrayList方がはるかに高速です。

int n = 100000000;
boolean[] primes = new boolean[n + 1];
for (int i = 0; i <= n; i++)
    primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 1; i <= n / 6; i++) {
    int prod6k = 6 * i;
    primes[prod6k + 1] = true;
    primes[prod6k - 1] = true;
}
for (int i = 0; i <= n; i++) {
    if (primes[i]) {
        int k = i;
        for (int j = k * k; j <= n && j > 0; j += k) {
               primes[j] = false;
        }
      }
}
for (int i = 0; i <= n; i++)
    if (primes[i]) 
        System.out.print(i + " ");
4

9 に答える 9

1

2 と 4 を交互に追加して、6 * k +/- 1 の乗算をなくすホイールを使用して試行番号を生成できます。

public void primesTo1000() {
  Set<Integer> notPrimes = new HashSet<>();
  ArrayList<Integer> primes = new ArrayList<>();
  primes.add(2);  //explicitly add
  primes.add(3);  //2 and 3

  int step = 2;
  int num = 5  // 2 and 3 already handled.
  while (num < 1000) {     
    handlePossiblePrime(num, primes, notPrimes);
    num += step;      // Step to next number.
    step = 6 - step;  // Step by 2, 4 alternately.
  }
  System.out.println(primes);
}
于 2015-08-05T20:15:30.023 に答える
1

このアプローチをさらに最適化できますか?

答えはイエスです。

特定の範囲内の数値のサブセットでふるいを使用することをお勧めします。あなたの提案はまさにそれを行っています。

プライムの生成について読む：

...さらに、ふるい形式に基づいて、いくつかの整数シーケンス ( OEIS のシーケンスA240673 ) が構築され、特定の間隔で素数を生成するためにも使用できます。

この段落の意味は、縮小された整数のリストから始めるというあなたのアプローチは確かにアカデミーによって採用されたが、彼らのテクニックはより効率的であるということです (しかし、当然、より複雑でもあります)。

于 2015-08-05T16:45:42.570 に答える