Encuentre la suma de los valores de N en cada paso después de dividirlo repetidamente por su factor más pequeño

Dado un número entero N , la tarea es encontrar la suma de todos los valores de N después de dividirlo repetidamente por su factor más pequeño.

Ejemplos:

Entrada: N = 5
Salida: 6
Explicación: Inicialmente N = 5. El factor más pequeño de N es 5 mismo. Por lo tanto, el valor de N será N/5 = 5/5 = 1. Por lo tanto, la suma de todos los valores de N es 5 + 1 = 6.

Entrada: N = 10.
Salida: 16
Explicación: Inicialmente N = 10. El factor más pequeño de N es 2. Por lo tanto, el valor de N será N/2 = 10/2 = 5. De manera similar, en el siguiente paso, N = N/5 = 5/5 = 1. Por lo tanto, la suma de todos los valores de N es 10 + 5 + 1 = 16.

Enfoque: El problema dado es un problema basado en la implementación y se puede resolver iterando en el rango [2, √N] y dividiendo N con su factor más pequeño , el máximo de veces posible. Mantener la suma de todos los valores de N en una variable que será la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum of all the
// values of N after repeatedly dividing
// it with its smallest factor
int sumValues(int N)
{
    // Stores the required answer
    int ans = N;
 
    int i = 2;
 
    // Loop to iterate over
    // the factors of N
    while (N > 1) {
 
        // If i is a factor
        if (N % i == 0) {
 
            // Update N
            N = N / i;
 
            // Update ans
            ans += N;
        }
        else {
            i++;
        }
    }
 
    // Return Answer
    return ans;
}
 
// Driver function
int main()
{
    int N = 10;
    cout << sumValues(N);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to find the sum of all the
  // values of N after repeatedly dividing
  // it with its smallest factor
  static int sumValues(int N)
  {
    // Stores the required answer
    int ans = N;
 
    int i = 2;
 
    // Loop to iterate over
    // the factors of N
    while (N > 1) {
 
      // If i is a factor
      if (N % i == 0) {
 
        // Update N
        N = N / i;
 
        // Update ans
        ans += N;
      }
      else {
        i++;
      }
    }
 
    // Return Answer
    return ans;
  }
 
  // Driver function
  public static void main (String[] args) {
    int N = 10;
    System.out.println(sumValues(N));
  }
}
 
// This code is contributed by hrithikgarg03188.

# python3 program for the above approach
 
# Function to find the sum of all the
# values of N after repeatedly dividing
# it with its smallest factor
def sumValues(N):
 
    # Stores the required answer
    ans = N
 
    i = 2
 
    # Loop to iterate over
    # the factors of N
    while (N > 1):
 
        # If i is a factor
        if (N % i == 0):
 
            # Update N
            N = N // i
 
            # Update ans
            ans += N
 
        else:
            i += 1
 
    # Return Answer
    return ans
 
# Driver function
if __name__ == "__main__":
 
    N = 10
    print(sumValues(N))
 
# This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG
{
   
// Function to find the sum of all the
// values of N after repeatedly dividing
// it with its smallest factor
static int sumValues(int N)
{
   
    // Stores the required answer
    int ans = N;
 
    int i = 2;
 
    // Loop to iterate over
    // the factors of N
    while (N > 1) {
 
        // If i is a factor
        if (N % i == 0) {
 
            // Update N
            N = N / i;
 
            // Update ans
            ans += N;
        }
        else {
            i++;
        }
    }
 
    // Return Answer
    return ans;
}
 
// Driver function
public static void Main()
{
    int N = 10;
    Console.Write(sumValues(N));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
      // JavaScript code for the above approach
 
      // Function to find the sum of all the
      // values of N after repeatedly dividing
      // it with its smallest factor
      function sumValues(N) {
          // Stores the required answer
          let ans = N;
 
          let i = 2;
 
          // Loop to iterate over
          // the factors of N
          while (N > 1) {
 
              // If i is a factor
              if (N % i == 0) {
 
                  // Update N
                  N = Math.floor(N / i);
 
                  // Update ans
                  ans += N;
              }
              else {
                  i++;
              }
          }
 
          // Return Answer
          return ans;
      }
 
      // Driver function
 
      let N = 10;
      document.write(sumValues(N));
 
     // This code is contributed by Potta Lokesh
  </script>

16

Complejidad de Tiempo: O(√N)
Espacio Auxiliar: O(1)