Tổng lớn nhất sau khi liên tục chia N cho ước số trong C++

Trong bài toán này, ta được cho một số nguyên N. Nhiệm vụ: viết chương trình tìm tổng lớn nhất sau khi liên tục chia N cho một ước số trong C++.

Mô tả – chia số N đệ quy cho đến khi thành 1, sau đó cộng tất cả các ước số và tìm tổng lớn nhất.

Hãy xem ví dụ:

Input – N = 12

Output – 22

Giải thích** – chia đệ quy và tính tổng:

Chia 1: 12/2 = 6 Chia 2: 6/2 = 3 Chia 3: 3/3 = 1 Tổng = 12+6+3+1 = 22

Để giải quyết, ta tìm tổng lớn nhất bằng cách làm cho các giá trị riêng lẻ lớn nhất bằng cách chia N cho ước số nhỏ nhất của N.

Ví dụ

Chương trình minh họa giải pháp:

#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<<"Tổng lớn nhất sau khi liên tục chia "<<N<<" cho ước số là "<<calculateMaxSum(N);    return 0; }

Kết quả

Tổng lớn nhất sau khi liên tục chia 12 cho ước số là 22