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 10Entrada : 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++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción
7
Complejidad temporal: O(sqrt(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por antriksh1685 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA