Dado un número entero N . La tarea es encontrar la suma máxima posible de valores intermedios (incluidos N y 1 ) obtenidos después de aplicar la siguiente operación:
Divide N entre cualquier divisor (>1) hasta que sea 1.
Ejemplos:
Input: N = 10 Output: 16 Initially, N=10 1st Division -> N = 10/2 = 5 2nd Division -> N= 5/5 = 1 Input: N = 8 Output: 15 Initially, N=8 1st Division -> N = 8/2 = 4 2nd Division -> N= 4/2 = 2 3rd Division -> N= 2/2 = 1
Enfoque: dado que la tarea es maximizar la suma de valores después de cada paso, intente maximizar los valores individuales. Entonces, reduzca el valor de N lo menos posible. Para lograr eso, dividimos N por su divisor más pequeño.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the smallest divisor int smallestDivisor(int n) { int mx = sqrt(n); for (int i = 2; i <= mx; i++) if (n % i == 0) return i; return n; } // Function to find the maximum sum int maxSum(int n) { long long res = n; while (n > 1) { int divi = smallestDivisor(n); n /= divi; res += n; } return res; } // Driver Code int main() { int n = 34; cout << maxSum(n); return 0; }
C
// C implementation of the above approach #include <stdio.h> #include<math.h> // Function to find the smallest divisor int smallestDivisor(int n) { int mx = sqrt(n); for (int i = 2; i <= mx; i++) if (n % i == 0) return i; return n; } // Function to find the maximum sum int maxSum(int n) { long long res = n; while (n > 1) { int divi = smallestDivisor(n); n /= divi; res += n; } return res; } // Driver Code int main() { int n = 34; printf("%d",maxSum(n)); return 0; } // This code is contributed by allwink45.
Java
// Java implementation of the above approach import java.io.*; class GFG { // Function to find the smallest divisor static double smallestDivisor(int n) { double mx = Math.sqrt(n); for (int i = 2; i <= mx; i++) if (n % i == 0) return i; return n; } // Function to find the maximum sum static double maxSum(int n) { long res = n; while (n > 1) { double divi = smallestDivisor(n); n /= divi; res += n; } return res; } // Driver Code public static void main (String[] args) { int n = 34; System.out.println (maxSum(n)); } } // This code is contributed by jit_t.
Python3
from math import sqrt # Python 3 implementation of the above approach # Function to find the smallest divisor def smallestDivisor(n): mx = int(sqrt(n)) for i in range(2, mx + 1, 1): if (n % i == 0): return i return n # Function to find the maximum sum def maxSum(n): res = n while (n > 1): divi = smallestDivisor(n) n = int(n/divi) res += n return res # Driver Code if __name__ == '__main__': n = 34 print(maxSum(n)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the above approach using System; class GFG { // Function to find the smallest divisor static double smallestDivisor(int n) { double mx = Math.Sqrt(n); for (int i = 2; i <= mx; i++) if (n % i == 0) return i; return n; } // Function to find the maximum sum static double maxSum(int n) { long res = n; while (n > 1) { double divi = smallestDivisor(n); n /= (int)divi; res += n; } return res; } // Driver Code public static void Main() { int n = 34; Console.WriteLine(maxSum(n)); } } // This code is contributed by Ryuga.
PHP
<?php // PHP implementation of the above approach // Function to find the smallest divisor function smallestDivisor($n) { $mx = sqrt($n); for ($i = 2; $i <= $mx; $i++) if ($n % $i == 0) return $i; return $n; } // Function to find the maximum sum function maxSum($n) { $res = $n; while ($n > 1) { $divi = smallestDivisor($n); $n /= $divi; $res += $n; } return $res; } // Driver Code $n = 34; echo maxSum($n); #This code is contributed by akt_mit. ?>
Javascript
<script> // javascript implementation of the above approach // Function to find the smallest divisor function smallestDivisor(n) { var mx = Math.sqrt(n); for (i = 2; i <= mx; i++) if (n % i == 0) return i; return n; } // Function to find the maximum sum function maxSum(n) { var res = n; while (n > 1) { var divi = smallestDivisor(n); n /= divi; res += n; } return res; } // Driver Code var n = 34; document.write(maxSum(n)); // This code is contributed by Rajput-Ji </script>
52
Complejidad de tiempo: O(sqrt(n)*log(n)), donde n representa el entero dado.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA