C++で最大の積と合計がNに等しいNの4つの要素を見つけます

整数Nがあるとします。タスクは、Nのすべての因子を見つけ、-

• それらの4つの要素の合計はNに等しい

• 4つの要素の積が最大です

数が24であるとすると、積は1296になります。すべての因子が1、2、3、4、6、8、12、24であることがわかっているので、因子6を4回選択する必要があります。したがって、6 + 6 + 6 + 6 =24です。ここでは、積が最大になります。

これを解決するには、1からNまでのすべての要素を見つけてから、これらの条件を確認する必要があります

• Nが素数の場合、答えは偽になります

• 与えられたnが4で割り切れる場合、答えはx^4になります。ここで、nが4で割り切れるときのxは商です。

• その場合、答えを見つけることができる場合、答えには最後から3番目の要素を2回含める必要があります。次に、他の2つの要素に対してネストされたループを実行します。

例

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool isPrime(int n) {
   if (n <= 1)
      return false;
   if (n <= 3)
      return true;
   if (n % 2 == 0 || n % 3 == 0)
      return false;
   for (int i = 5; i * i <= n; i = i + 6)
      if (n % i == 0 || n % (i + 2) == 0)
   return false;
   return true;
}
void get_factors(int N, vector<int> fact_vectors[]) {
   for (int i = 2; i < N; i++) {
      for (int j = 1; j * j <= i; j++) {
         if (i % j == 0) {
            if (i / j == j)
            fact_vectors[i].push_back(j);
            else {
               fact_vectors[i].push_back(j);
               fact_vectors[i].push_back(i / j);
            }
         }
      }
      sort(fact_vectors[i].begin(), fact_vectors[i].end());
   }
}
int getProduct(int n) {
   vector<int> v[n + 100];
   get_factors(n + 100, v);
   if (n % 4 == 0) {
      int x = n / 4;
      x *= x;
      return x * x;
   } else {
      if (isPrime[n])
      return -1;
      else {
         int ans = -1;
            if (v[n].size() > 2) {
               int fac = v[n][v[n].size() - 3];
               for (int i = v[n].size() - 1; i >= 0; i--) {
                  for (int j = v[n].size() - 1; j >= 0; j--) {
                     if ((fac * 2) + (v[n][j] + v[n][i]) == n)
                     ans = max(ans, fac * fac * v[n][j] * v[n][i]);
                  }
               }
            return ans;
         }
      }
   }
}
int main() {
   int n = 24;
   cout << "The product is: " << getProduct(n);
}

出力

The product is: 1296