ในปัญหานี้ เราได้รับตัวเลข 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
