C++で与えられた数Nの約数で最大の良い数を見つけます

この問題では、数Nが与えられます。私たちのタスクは、与えられた数Nの約数で最大の適切な数を見つけることです。 。

かなりの数 は、すべての桁がその右側の桁の合計よりも大きい数値です（すべての桁数がそれよりも小さい）。たとえば、732は適切な数値であり、7> 3+2および3>2です。

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

Input : N = 15
Output : 15

説明 −

Divisors of 15 : 1, 3, 5, 15.

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

この問題の簡単な解決策は、Nのすべての約数を見つけることです。そして、その数のすべての素数の約数の積として抽出される最大の良い数を見つけます。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
int findLargestGoodNumber(int n){
   vector<int> primeFactors;
   int x = n;
   for (int i = 2; i * i <= n; i++) {
      if (x % i == 0) {
         primeFactors.push_back(i);
         while (x % i == 0) 
            x /= i;
      }
   }
   if (x > 1) 
      primeFactors.push_back(x);
   int goodNumber = 1;
   for (int i = 0; i < primeFactors.size(); i++)
      goodNumber = goodNumber * primeFactors[i];
   return goodNumber;
}
int main(){
   int n = 28;
   cout<<"The largest good Number in divisor of "<<n<<" is "<<findLargestGoodNumber(n); 
   return 0;
}

例

The largest good Number in divisor of 28 is 14