ผลรวมสูงสุดหลังจากการหาร N ซ้ำๆ ด้วยตัวหารใน C++

ในปัญหานี้ เราได้รับจำนวนเต็ม N หน้าที่ของเราคือสร้างโปรแกรมที่จะหาผลรวมสูงสุดหลังจากการหาร N ซ้ำๆ ด้วยตัวหารใน C++

คำอธิบายโปรแกรม − เราจะหารตัวเลข N ซ้ำๆ จนกลายเป็นหนึ่ง จากนั้นจึงรวมตัวหารทั้งหมดและหาค่าสูงสุดของตัวหารทั้งหมด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − N =12

ผลผลิต − 22

คำอธิบาย − ลองหารตัวเลขแบบวนซ้ำแล้วหาผลรวม

Division 1: 12/2 = 6
Division 2: 6/2 = 3
Division 3: 3/3 = 1
Sum = 12+6+3+1 = 22

ในการแก้ปัญหานี้ เราจะหาผลรวมสูงสุดโดยการทำให้ค่าสูงสุดแต่ละรายการหารด้วย N ด้วยตัวหารที่เล็กที่สุดของ N

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <bits/stdc++.h>
using namespace std;
int smallestDivisor(int n){
   int mx = sqrt(n);
   for (int i = 2; i <= mx; i++)
      if (n % i == 0)
         return i;
   return n;
}
int calculateMaxSum(int n) {
   long long maxSum = n;
   while (n > 1) {
      int divisor = smallestDivisor(n);
      n /= divisor;
      maxSum += n;
   }
   return maxSum;
}
int main(){
   int N = 12;
   cout<<"The maximum sum after repeatedly dividing "<<N<<" by divisor is "<<calculateMaxSum(N);
   return 0;
}

ผลลัพธ์

The maximum sum after repeatedly dividing 12 by divisor is 22