C++で数値に正確に4つの異なる要素があるかどうかを確認するためのクエリ

この問題では、Q個のクエリが与えられます。各クエリの数はNです。私たちのタスクは、クエリを解決するプログラムを作成して、C++で数に4つの異なる要素があるかどうかを確認することです。

問題の説明

各クエリを解決するには、数値Nに正確に4つの異なる因子があるかどうかを確認する必要があります。印刷が「はい」の場合は「いいえ」です。

問題を理解するために例を見てみましょう

入力 ：Q =3、4、6、15

出力 ：いいえはいはい

説明

クエリ1の場合：係数4は1、2、4

クエリ2の場合：6の因数は1、2、3、6

クエリ3の場合：15の因数は1、3、5、15

ソリューションアプローチ

この問題の簡単な解決策は、数のすべての要因を見つけることです。これは、1から√Nまでのすべての数値を見つけ、カウンターを2増やすことによって行われます。次に、カウンターが4に等しいかどうかを確認し、その等しいことに基づいてYESまたはNOを出力します。

例

#include <iostream>
#include <math.h>
using namespace std;
   int solveQuery(int N){
   int factors = 0;
   for(int i = 1; i < sqrt(N); i++){
      if(N % i == 0){
         factors += 2;
      }
   }
   if(factors == 4){
      return 1;
   }
   return 0;
}
int main() {
   int Q = 3;
   int query[3] = {4, 6, 15};
   for(int i = 0; i < Q; i++){
      if(solveQuery(query[i]))
         cout<<"The number "<<query[i]<<" has exactly four distinct factors\n";
      else
         cout<<"The number "<<query[i]<<" does not have exactly four
      distinct factors\n";
   }
}

出力

The number 4 does not have exactly four distinct factors
The number 6 has exactly four distinct factors
The number 15 has exactly four distinct factors

効率的なアプローチは、4因子数の数論の概念を使用することです。したがって、数値に4つの要素がある場合、

• 数が素数の立方体である場合。次に、4つの異なる要素があります。たとえば、N =（p ^ 3）の場合、係数は1、p、（p ^ 2）、Nになります。

• 数が2つの異なる素数の積である場合。次に、4つの異なる要素があります。たとえば、N =p1 * p2の場合、係数は1、p1、p2、Nになります。

例

#include <bits/stdc++.h>
using namespace std;
int N = 1000;
   bool hasFourFactors[1000];
   void fourDistinctFactors() {
      bool primeNo[N + 1];
      memset(primeNo, true, sizeof(primeNo));
      for (int i = 2; i <= sqrt(N); i++) {
         if (primeNo[i] == true) {
            for (int j = i * 2; j <= N; j += i)
               primeNo[j] = false;
         }
      }
      vector<int> primes;
      for (int i = 2; i <= N; i++)
         if (primeNo[i])
            primes.push_back(i);
            memset(hasFourFactors, false, sizeof(hasFourFactors));
   for (int i = 0; i < primes.size(); ++i) {
      int p1 = primes[i];
      if (1 *(pow(p1, 3)) <= N)
         hasFourFactors[p1*p1*p1] = true;
      for (int j = i + 1; j < primes.size(); ++j) {
         int p2 = primes[j];
         if (1 * p1*p2 > N)
            break;
         hasFourFactors[p1*p2] = true;
      }
   }
}
int main() {
   int Q = 3;
   int query[] = {3, 6, 15};
   fourDistinctFactors();
   for(int i = 0; i < Q; i++){
      if(hasFourFactors[query[i]])
         cout<<"The number "<<query[i]<<" has exactly four distinct
         factors\n";
      else
         cout<<"The number "<<query[i]<<" does not have exactly four distinct factors\n";
   }
   return 0;
}

出力

The number 3 does not have exactly four distinct factors
The number 6 has exactly four distinct factors
The number 15 has exactly four distinct factors