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