C++でNより大きいK番目の素数

このチュートリアルでは、与えられた数nより大きいk番目の素数を見つけるプログラムを作成します。

• 番号nを初期化します。
• 1e6までのすべての素数を見つけて、ブール配列に格納します。
• n+1から1e6まで繰り返すループを作成します。
  • 現在の数が素数の場合は、kをデクリメントします。
  • kがゼロに等しい場合は、iを返します。
• -1を返します。

例

コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 1e6;
bool prime[MAX_SIZE + 1];
void findAllPrimes() {
   memset(prime, true, sizeof(prime));
   for (int p = 2; p * p <= MAX_SIZE; p++) {
      if (prime[p]) {
         for (int i = p * p; i <= MAX_SIZE; i += p) {
            prime[i] = false;
         }
      }
   }
}
int findKthPrimeGreaterThanN(int n, int k) {
   for (int i = n + 1; i < MAX_SIZE; i++) {
      if (prime[i]) {
         k--;
      }
      if (k == 0) {
         return i;
      }
   }
   return -1;
}
int main() {
   findAllPrimes();
   int n = 5, k = 23;
   cout << findKthPrimeGreaterThanN(n, k) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

101

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。