Suma de todos los divisores primos de un número | conjunto 2

Dado un número N ,  la tarea es encontrar la suma de todos los factores primos de N.

Ejemplos:

Entrada : 10
Salida : 7
Explicación: 2, 5 son divisores primos de 10

Entrada : 20
Salida : 7
Explicación : 2, 5 son divisores primos de 20

Enfoque: Este problema se puede resolver encontrando todos los factores primos del número. Siga los pasos a continuación para resolver este problema:

• Inicialice una suma variable como 0 para almacenar la suma de los divisores primos de N.
• Si N es divisible por 2, suma 2 a la suma y divide N por 2 hasta que sea divisible.
• Iterar en el rango [3, sqrt(N)] usando la variable i, con un incremento de 2 :
  • Si N es divisible por i, agregue i a la suma y divida N por i hasta que sea divisible.
• Si N es un número primo mayor que 2, agregue N a la suma.
• Después de completar los pasos anteriores, imprima la suma como la respuesta.

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 sum of prime
// divisors of the given number N
int SumOfPrimeDivisors(int n)
{
 
    int sum = 0;
 
    // Add the number 2 if it divides N
    if (n % 2 == 0) {
        sum = sum + 2;
    }
 
    while (n % 2 == 0) {
        n = n / 2;
    }
 
    // Traverse the loop from [3, sqrt(N)]
    for (int i = 3; i <= sqrt(n); i = i + 2) {
 
        // If i divides N, add i and divide N
        if (n % i == 0) {
            sum = sum + i;
        }
 
        while (n % i == 0) {
            n = n / i;
        }
    }
 
    // This condition is to handle the case when N
    // is a prime number greater than 2
    if (n > 2) {
        sum = sum + n;
    }
 
    return sum;
}
 
// Driver code
int main()
{
    // Given Input
    int n = 10;
 
    // Function Call
    cout << SumOfPrimeDivisors(n);
    return 0;
}

// Java program for the above approach
 
import java.io.*;
 
class GFG {
  // Function to find sum of prime
  // divisors of the given number N
  public static int SumOfPrimeDivisors(int n)
  {
 
    int sum = 0;
 
    // Add the number 2 if it divides N
    if (n % 2 == 0) {
      sum = sum + 2;
    }
 
    while (n % 2 == 0) {
      n = n / 2;
    }
 
    // Traverse the loop from [3, sqrt(N)]
    for (int i = 3; i <= Math.sqrt(n); i = i + 2) {
 
      // If i divides N, add i and divide N
      if (n % i == 0) {
        sum = sum + i;
      }
 
      while (n % i == 0) {
        n = n / i;
      }
    }
 
    // This condition is to handle the case when N
    // is a prime number greater than 2
    if (n > 2) {
      sum = sum + n;
    }
 
    return sum;
  }
 
  // Driver code
  public static void main (String[] args)
  {
 
    // Given Input
    int n = 10;
 
    // Function Call
    System.out.println(SumOfPrimeDivisors(n));
  }
}
 
// This code is contributed by Potta Lokesh

# Python3 program for the above approach
import math
 
# Function to find sum of prime
# divisors of the given number N
def SumOfPrimeDivisors(n):
     
    sum = 0
     
    # Add the number 2 if it divides N
    if n % 2 == 0:
        sum += 2
         
    while n % 2 == 0:
        n //= 2
         
    # Traverse the loop from [3, sqrt(N)]
    k = int(math.sqrt(n))
     
    for i in range(3, k + 1, 2):
         
        # If i divides N, add i and divide N
        if n % i == 0:
            sum += i
             
        while n % i == 0:
            n //= i
             
    # This condition is to handle the case when N
    # is a prime number greater than 2
    if n > 2:
        sum += n
         
    # Return the sum
    return sum
 
# Driver code
if __name__ == '__main__':
     
    # Given input
    n = 10
     
    # Function call
    print(SumOfPrimeDivisors(n))
     
# This code is contributed by MuskanKalra1

// C# program for the above approach
 
using System;
 
class GFG {
  // Function to find sum of prime
  // divisors of the given number N
  public static int SumOfPrimeDivisors(int n)
  {
 
    int sum = 0;
 
    // Add the number 2 if it divides N
    if (n % 2 == 0) {
      sum = sum + 2;
    }
 
    while (n % 2 == 0) {
      n = n / 2;
    }
 
    // Traverse the loop from [3, sqrt(N)]
    for (int i = 3; i <= Math.Sqrt(n); i = i + 2) {
 
      // If i divides N, add i and divide N
      if (n % i == 0) {
        sum = sum + i;
      }
 
      while (n % i == 0) {
        n = n / i;
      }
    }
 
    // This condition is to handle the case when N
    // is a prime number greater than 2
    if (n > 2) {
      sum = sum + n;
    }
 
    return sum;
  }
 
  // Driver code
  public static void Main (String[] args)
  {
 
    // Given Input
    int n = 10;
 
    // Function Call
    Console.Write(SumOfPrimeDivisors(n));
  }
}
 
// This code is contributed by shivanisinghss2110

<script>
        // JavaScript program for the above approach
 
        // Function to find sum of prime
        // divisors of the given number N
        function SumOfPrimeDivisors(n) {
 
            let sum = 0;
 
            // Add the number 2 if it divides N
            if (n % 2 == 0) {
                sum = sum + 2;
            }
 
            while (n % 2 == 0) {
                n = n / 2;
            }
 
            // Traverse the loop from [3, sqrt(N)]
            for (let i = 3; i <= Math.sqrt(n); i = i + 2) {
 
                // If i divides N, add i and divide N
                if (n % i == 0) {
                    sum = sum + i;
                }
 
                while (n % i == 0) {
                    n = n / i;
                }
            }
 
            // This condition is to handle the case when N
            // is a prime number greater than 2
            if (n > 2) {
                sum = sum + n;
            }
 
            return sum;
        }
 
        // Driver code
 
        // Given Input
        let n = 10;
 
        // Function Call
        document.write(SumOfPrimeDivisors(n));
 
// This code is contributed by Potta Lokesh
 
    </script>

7

Complejidad temporal: O(sqrt(N))
Espacio auxiliar: O(1)