C++でN以下のすべての半素数を出力します

この問題では、整数Nが与えられ、N以下のすべての半素数を出力する必要があります。

この問題を解決する前に、半素数とは何かを理解しましょう。

半素数 は、値が2つの異なる素数の積である数です。

例を見てみましょう

21 =3*7は半素数です。

25 =5*5は半素数ではありません。

それでは、n以下の半素数の例を見てみましょう。

Input: N = 15
Output: 6 10 14 15

この問題を解決するには、N以下の各数を取り、それが正確に2つの異なる素因数を持っているかどうかを確認する必要があります。

ヒント −最小の半素数は6であるため、アルゴリズムを6から開始することもできます。

例

#include <bits/stdc++.h>
using namespace std;
vector<int>generateSemiPrimeNumbers(int n){
   int index[n + 1];
   for (int i = 1; i <= n; i++)
      index[i] = i;
   int countDivision[n + 1];
   for (int i = 0; i < n + 1; i++)
      countDivision[i] = 2;
   for (int i = 2; i <= n; i++) {
      if (index[i] == i && countDivision[i] == 2) {
         for (int j = 2 * i; j <= n; j += i) {
            if (countDivision[j] > 0) {
               index[j] = index[j] / i;
               countDivision[j]--;
            }
         }
      }
   }
   vector<int> semiPrime;
   for (int i = 2; i <= n; i++) {
      if (index[i] == 1 && countDivision[i] == 0) semiPrime.push_back(i);
   }
   return semiPrime;
}
int main(){
   int n = 15;
   cout<<"Semi-prime numbers less that or equal to "<<n<<"are :\n";
   vector<int>semiPrime = generateSemiPrimeNumbers(n);
   for (int i = 0; i < semiPrime.size(); i++)
      cout<<semiPrime[i]<<"\t";
   return 0;
}

出力

15以下の半素数は-

6 10 14 15