8

素数を見つけるために多くのアルゴリズムを読みましたが、結論は、前の素数のいずれでも割り切れない場合、数値は素数であるということです。

より正確な定義を見つけることができません。これに基づいてコードを書きましたが、渡す最大数が 1000000 になるまで満足のいくパフォーマンスを発揮します。

以下は私のコードですが、同じバージョンのより良いバージョンを入手できますか?

 public static void main(String[] args) {
    for (int i = 2; i < 100000; i++) {
        if (checkMod(i)) {
            primes.add(i);
        }
    }
}

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}
4

7 に答える 7

21

素数性テストの良いところは、素数だけで除算することです。

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

悪い点は、これまでに見つかったすべての素数、つまり候補よりも小さいすべての素数で除算することです。つまり、100 万未満の最大の素数 999983 を 78497 の素数で割ると、この数が素数であることがわかります。それは大変な作業です。実際、このアルゴリズムで素数に費やされる作業は、100 万に達すると全作業の約 99.9% を占め、上限が高くなるほど大きくなります。そして、そのアルゴリズムはほぼ 2 次nです。このように素数を見つけるには、約実行する必要があります。

n² / (2*(log n)²)

部門。

簡単な改善は、分割を早期に停止することです。nを合成数 (つまり、1 と 以外の約数を持つ 1 より大きい数)nとし、 をdの約数としnます。

ここでd、 の除数であるnことn/dは、 が整数であり、 : の除数であるnことを意味しますn/(n/d) = d。したがって、自然に のn除数をペアにグループ化することができ、各除数dはペア を生じさせ(d, n/d)ます。

このようなペアには、次の 2 つの可能性があります。

  1. d = n/dn = d²、またはを意味しd = √nます。
  2. 2つは異なり、一方は他方よりも小さく、たとえばd < n/d. しかし、それはすぐにd² < norに変換されd < √nます。

したがって、いずれの場合も、除数の各ペアには (少なくとも) を超えないものが含まれます√n。したがって、が合成数である場合n、その最小の除数 (1 以外) は を超えません√n。

したがって、到達したら試行分割を停止できます√n。

private static boolean checkMod( int num) {
    for (int i : primes){
        if (i*i > n){
            // We have not found a divisor less than √n, so it's a prime
            return true;
        }
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

注: これは、昇順で繰り返される素数のリストに依存します。それが言語によって保証されていない場合は、別の方法を使用する必要がありますArrayList。

100 万未満の最大の素数 999983 の候補の平方根で試行分割を停止すると、1000 未満の 168 の素数で除算するだけで済みます。これは以前よりもはるかに少ない作業です。試行分割を平方根で停止し、素数のみで割ることは、試行分割が可能な限り良好であり、約必要です。

2*n^1.5 / (3*(log n)²)

の場合n = 1000000、それは約 750 倍です。悪くないですね。

しかし、それはまだあまり効率的ではありません。以下のすべての素数を見つける最も効率的な方法nはふるいです。簡単に実装できるのは、古典的なエラトステネスのふるいです。これにより、O(n*log log n) 操作で以下の素数が検出nされ、いくつかの機能強化 (いくつかの小さな素数の倍数を事前に考慮から除外する) により、その複雑さを O(n) 操作に減らすことができます。より良い漸近挙動を持つ比較的新しいふるいは、アトキンのふるいです。nO(n) 操作で、または O(n/log log n) 操作で、いくつかの小さな素数の倍数を除去する拡張機能を使用します。アトキンのふるいは実装がより複雑であるため、エラトステネスのふるいの適切な実装は、アトキンのふるいの素朴な実装よりも優れたパフォーマンスを発揮する可能性があります。同様の最適化レベルの実装では、制限が大きくならない限り (10 10; 実際には、メモリ アクセス パターンが優れているため、エラトステネスのふるいの方がアトキンのふるいよりも優れていることは珍しくありません)。したがって、エラトステネスのふるいから始めることをお勧めします。最適化に向けた誠実な努力にもかかわらず、そのパフォーマンスが満足のいくものではない場合にのみ、アトキンのふるいを掘り下げます。または、自分で実装したくない場合は、他の誰かがすでに真剣に調整している適切な実装を見つけてください。

問題がn番目の素数を見つけることであった、わずかに異なる設定の回答でもう少し詳しく説明しました。多かれ少なかれ効率的な方法のいくつかの実装は、その回答からリンクされています。特に、エラトステネスのふるいの1つまたは2つの使用可能な（あまり最適化されていませんが）実装です。

于 2012-05-21T22:01:26.740 に答える
1

私はいつもエラトステネスのふるいを使っています。

isPrime[100001] // - initially contains only '1' values (1,1,1 ... 1)
isPrime[0] = isPrime[1] = 0 // 0 and 1 are not prime numbers

primes.push(2); //first prime number. 2 is a special prime number because is the only even prime number.
for (i = 2; i * 2 <= 100000; i++) isPrime[i * 2] = 0 // remove all multiples of 2

for (i = 3; i <= 100000; i += 2) // check all odd numbers from 2 to 100000
    if (isPrime[i]) {
        primes.push(i); // add the new prime number to the solution
        for (j = 2; i * j <= 100000; j++) isPrime[i * j] = 0; // remove all i's multiples
    }

return primes

私のコメントを理解していただければ幸いです

于 2012-05-21T18:58:58.233 に答える
0

上記の Benjamin Oman によって提案された 0ne をさらにわずかに改善したバージョンを作成したいと思います。これは、数字 '5' で終わるすべての数字の素数のチェックを回避するための 1 つの変更にすぎません。 5までに。

for (int i = 7;(i < 100000) && (!i%5==0); i = i + 2) {
    if (checkMod(i)) {
        primes.add(i);
    }
}

これは、2、3、5 が素数であるという仮定に基づいています。上記の小さな変更により、すべての要因が 5 分の 1 に減少し、改善されます。

于 2014-02-02T06:46:55.817 に答える
0

@Daniel Fischerによってうまく説明されています。

彼の説明からの C++ での実装:

#include<iostream>

using namespace std;

long* getListOfPrimeNumbers (long total)
{
  long * primes;
  primes = new long[total];
  int count = 1;
  primes[0] = 2;
  primes[1] = 3;
  while (count < total)
  {
    long composite_number = primes[count] + 2;
    bool is_prime = false;
    while (is_prime == false)
    {
      is_prime = true;
      for (int i = 0; i <= count; i++)
      {
        long prime = primes[i];
        if (prime * prime > composite_number)
        {
          break;
        }
        if (composite_number % prime == 0)
        {
          is_prime = false;
          break;
      }
      }
      if (is_prime == true)
      {
        count++;
        primes[count] = composite_number;
      }
      else
      {
        composite_number += 2;
    }
  }
  }
  return primes;
}

int main()
{
  long * primes;
  int total = 10;
  primes = getListOfPrimeNumbers(total);
  for (int i = 0; i < total; i++){
    cout << primes[i] << "\n";
  }
  return 0;
}
于 2014-03-30T17:01:02.330 に答える
0

素数とは、それ自体と数字 1 だけで割り切れる (剰余がない) 数字であると理解しています。ウィキペディアの記事を参照

そうは言っても、2 番目のコメントではアルゴリズムがよくわかりませんが、アルゴリズムの小さな改善点の 1 つは、for ループを次のように変更することです。

for (int i = 5; i < 100000; i = i + 2) {
    if (checkMod(i)) {
        primes.add(i);
    }
}

これは、1、2、3 はすべて素数であり、それ以降のすべての偶数は素数ではないという仮定に基づいています。これにより、アルゴリズムが少なくとも半分になります。

于 2012-05-21T19:01:07.903 に答える