用 C++ 打印所有小于等于 N 的半素数

在这个问题中，我们给定一个整数 N，我们需要打印所有小于等于 N 的半素数。

在解决这个问题之前，让我们先了解什么是半素数。

半素数是一个其值为两个不同素数的乘积的数。

让我们举个例子，

21 = 3*7 是一个半素数。

25 = 5*5 不是一个半素数。

现在，让我们举一个小于等于 n 的半素数的例子。

Input: N = 15
Output: 6 10 14 15

要解决这个问题，我们必须取每个小于等于 N 的数，并检查它是否正好有两个不同的素数因子。

提示 - 我们也可以从 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

更新于: 2020年1月17日

359 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告