C++ の素数ジェネレーター

1. 素数
2. C++ で素数を生成する
3. sqrt() メソッドを使用して C++ で素数を生成する

このクイック プログラミング チュートリアルでは、シンプルで直感的な方法と効率的な平方根法を使用して、特定の範囲内のすべての素数を生成する方法について説明します。

素数

素数は、1 で割り切れるか、それ自体でのみ割り切れる数です。 たとえば、17 は 1 またはそれ自体でしか割り切れない数です。 素数 P の因数は P * 1 だけです。

素数の集合を見てみましょう。

Set of Prime Numbers = {2, 3, 5 , 7, 11, 13, 17, 23, .....,89, 97, .... }

C++ では、このようなシナリオをコーディングして、ある範囲内で素数を生成し、数値が素数であるかどうかを確認することもできます。

C++ で素数を生成する

数値が素数であるかどうかをチェックする背後にあるロジックは、その数値の半分までのすべての数値でモジュラスをチェックすることです。 いずれかの数値のモジュラスが 0 の場合、その数値は素数ではありません。 それ以外の場合は素数です。

最も単純で直感的な方法を見てみましょう。

#include <iostream>
using namespace std;

int main() {
  int start = 0, end = 100, n;
  bool ifPrime = true;

  cout << "Prime numbers in between " << start << " and " << end
       << " are the following: " << endl;

  while (start < end) {
    ifPrime = true;

    if (start == 0 || start == 1) {
      ifPrime = false;
    }

    for (n = 2; n <= start / 2; ++n) {
      if (start % n == 0) {
        ifPrime = false;
        break;
      }
    }
    if (ifPrime) cout << start << ", ";

    ++start;
  }

  return 0;
}

上記のコード セグメントでは、start と end という 2つの変数を使用しています。 start 変数は 0 に初期化され、end 変数は 100 に初期化されます。これは、0 から 100 までの素数が必要だからです。

この範囲はいつでも変更でき、ユーザーからの入力として取得することもできます。

start から end までのループを作成しました。 そのループで、別の for ループを作成して、start の数値がこの数値の半分までの数値で割り切れるかどうかを確認しました。 これは、非素数 N の場合、a*b で a<N/2 および b<N/2 となるような数値 a と b の因数しか存在しないためです。

したがって、内側の for ループで n が start 値の半分に近づくと、ループは終了し、ifprime はまだ true であるため、25 行目で数値が出力されます。 ただし、n のいずれかの値が start の値を適切に分割する場合、19 行目の条件は true になり、ifprime を false に設定し、for ループを終了します。

出力：

sqrt() メソッドを使用して C++ で素数を生成する

前に説明した単純な素数の計算方法は、素数かどうかを確認するために数の半分まで割る必要があるため、非効率的でした。 ただし、数学的事実を利用して、プログラムの実行時間の複雑さを軽減できます。

このプログラムは、係数 a*b が数値 N に等しくなるためには、a または b のいずれかが N の平方根以下でなければならないという事実を利用しています。 たとえば、36 の場合、考えられる因子のペアは (9*4)、(18*2)、(12*3)、(6*6) であるため、すべてのペアには a があります。 または b は 36 の平方根未満です。

したがって、数値 N が素数ではないことを認めないためには、N の平方根より小さい任意の数で割り切れるかどうかを確認するだけで済みます。 そうでない場合は、その数が素数であることを意味します。

それでは、シナリオをコーディングしましょう。

#include <math.h>

#include <iostream>
using namespace std;

int main() {
  int start = 0, end = 100, n;
  bool ifPrime = true;

  cout << "Prime numbers in between " << start << " and " << end
       << " are the following: " << endl;

  while (start < end) {
    ifPrime = true;

    if (start == 0 || start == 1) {
      ifPrime = false;
    }

    for (n = 2; n <= sqrt(start); ++n) {
      if (start % n == 0) {
        ifPrime = false;
        break;
      }
    }
    if (ifPrime) cout << start << ", ";

    ++start;
  }

  return 0;
}

start から end までのループを作成しました。そのループでは、内側のループの切り捨て数となる数値の平方根を取得します。

内側のループは、現在の数値が平方根までの任意の数値で割り切れるかどうかをチェックします。 そうでない場合は、素数として出力します。

出力：