Cプログラミングのスーパー素数

スーパープライム番号は、すべての素数のシーケンスで素数の位置を占める番号です。高次素数とも呼ばれます。これらの数は、素数と等しい素数のシーケンスの位置を占めます。いくつかの超素数は3,5,11,17…

たとえば、13未満のすべての超素数を見つけましょう-

入力

13

出力

3, 5, 11.

説明 − 13未満の超素数を見つけるには、13未満のすべての素数を見つけます。したがって、13未満のすべての素数が2、3、5、7、11、13であることを示します。ここで、2は素数なので、位置toの素数をスーパー素数と見なします。これは、3が素数であることを意味します。同様に、位置3の5と位置5の11は超素数です。

指定された素数よりも小さいすべての素数を見つけるには、最初にその数よりも小さいすべての素数を見つけてから、配列に格納します。この配列からは、位置がいずれかの素数と等しい数のみが出力されます。たとえば、2番目、3番目、5番目、7番目、11番目、13番目の素数…。考慮されます。

例

#include<iostream>
using namespace std;
bool SieveOfEratosthenes(int n, bool isPrime[]) {
   isPrime[0] = isPrime[1] = false;
   for (int i=2; i<=n; i++)
      isPrime[i] = true;
   for (int p=2; p*p<=n; p++) {
      if (isPrime[p] == true) {
         for (int i=p*2; i<=n; i += p)
            isPrime[i] = false;
      }
   }
}
void superPrimes(int n) {
   bool isPrime[n+1];
   SieveOfEratosthenes(n, isPrime);
   int primes[n+1], j = 0;
   for (int p=2; p<=n; p++)
      if (isPrime[p])
   primes[j++] = p;
   for (int k=0; k<j; k++)
      if (isPrime[k+1])
   cout << primes[k] << " ";
}
int main() {
   int n = 343;
   cout << "Super-Primes less than "<< n << " are :"<<endl;
   superPrimes(n);
   return 0;
}

出力

Super-Primes less than 343 are :
3 5 11 17 31 41 59 67 83 109 127 157 179 191 211 241 277 283 331