素数判定アルゴリズム小結

1352 ワード
コードの巡礼路
素数アルゴリズム小結
多くのプログラムの设计のテーマはすべて素数の判定アルゴリズムを使う必要があることを発见して、私も多くのことに出会ったことがあって、ある时は时间の复雑さに対して厳格な要求がなくて、この时私达は时に简単な判定アルゴリズムでいいですが、时には时间の要求に対してとても厳格で、この时にいくつかの改善と最適化が必要です.
素数の定義:1とそれ自体を除いて、他のすべての数によって除去することはできません;
次に、私が知っているアルゴリズムをまとめます.
  • 最も簡単な判断:定義によると、私たちは2からnまで終了し、循環判断をすればよい.
    bool flag = true;
for (int i = 2; i < n; i++)
{
 if (n % i == 0)
 {
     flag = false;
     break;
 }
}
  • 簡易判定の最適化:被除数判定範囲を2~sqrt(n) 
    bool flag = true;
for (int i = 2; i <= sqrt(n); i++)
{
 if (n % i == 0)
 {
     flag = false;
     break;
 }
}
    • に絞る.
  • 素数最適化を利用する:判定範囲をn未満の素数すべてに縮小し、1つの数がすべての素数で除去できない場合、それ自体も素数
    vector v;
v.push_back(2);
for (int i = 3; i < N; i++)
{
 bool flag = true;
 for (vector::const_iterator it = v.begin(); *it <= sqrt(i); it++)
 {
     if (i % *it == 0)
     {
         flag = false;
         break;
     }
 }
 if (flag)
 {
     v.push_back(i);
 }
}
    • である.
  • スクリーニングアルゴリズム:2から、その2~m倍の数のタグをnにループすると、タグなしの数は素数
    bool *array = new int[n];
for (int i = 2; i < n; i++)
{
 for (int j = 2; i * j < n; j++)
 {
     array[i * j] = false;
 }
}
    • となる.
  • 素数表:2~nのすべての素数を表に記録し、必要に応じて表table[i]を調べると
    • が得られる.
  • Ferma小定理
    • なぜJDKでStringクラスのindexofはKMPやBoyer-Mooreなどの時間的複雑度の低いアルゴリズムを使用しないのか
    ビッグデータプラットフォームの下でSparkが製品の推薦を行う