In tất cả các số bán nguyên tố nhỏ hơn hoặc bằng N trong C ++

Trong bài toán này, chúng ta được cho một số nguyên N. và chúng ta phải in ra tất cả các số bán chuẩn nhỏ hơn hoặc bằng N.

Trước khi giải quyết vấn đề này, hãy hiểu thế nào là số bán nguyên tố.

Một số bán nguyên tố là một số có giá trị là tích của hai số nguyên tố phân biệt.

Hãy lấy một ví dụ,

21 =3 * 7 là số bán chuẩn.

25 =5 * 5 không phải là số bán chuẩn.

Bây giờ, hãy lấy một ví dụ về các số bán chuẩn nhỏ hơn hoặc bằng n.

Input: N = 15
Output: 6 10 14 15

Để giải quyết vấn đề này, chúng ta phải lấy mỗi số nhỏ hơn N và kiểm tra xem nó có đúng hai thừa số nguyên tố phân biệt hay không.

Mẹo - chúng ta cũng có thể bắt đầu thuật toán của mình từ 6 vì số bán nguyên tố nhỏ nhất là 6.

Ví dụ

#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;
}

Đầu ra

Các số bán nguyên tố nhỏ hơn hoặc bằng 15 là -

6 10 14 15