C++에서 N보다 작거나 같은 모든 반소수 인쇄

이 문제에서는 정수 N이 주어지고 N보다 작거나 같은 모든 반소수를 출력해야 합니다.

이 문제를 풀기 전에 반소수(semi-prime number)가 무엇인지 이해합시다.

반소수 값이 서로 다른 두 소수의 곱인 숫자입니다.

예를 들어 보겠습니다.

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