Dado un número n, la tarea es encontrar la suma par de un número.
Ejemplos:
Input : 30 Output : 48 Even dividers sum 2 + 6 + 10 + 30 = 48 Input : 18 Output : 26 Even dividers sum 2 + 6 + 18 = 26
Requisito previo: Suma de factores
Como se discutió en la publicación anterior mencionada anteriormente, la suma de factores de un número es
Sean p1, p2, … pk factores primos de n. Sean a1, a2, ..ak potencias máximas de p1, p2, ..pk respectivamente que dividen n, es decir, podemos escribir n como n = (p1 a1 )*(p2 a2 )* … (pk ak ) .
Sum of divisors = (1 + p1 + p12 ... p1a1) *
(1 + p2 + p22 ... p2a2) *
...........................
(1 + pk + pk2 ... pkak)
Si el número es impar, entonces no hay factores pares, por lo que simplemente devolvemos 0.
Si el número es par, usamos la fórmula anterior. Solo necesitamos ignorar 2 0 . Todos los demás términos se multiplican para producir una suma de factores pares. Por ejemplo, considere n = 18. Se puede escribir como 2 1 3 2 y el sol de todos los factores es (2 0 + 2 1 )*(3 0 + 3 1 + 3 2 ). si eliminamos 2 0 , obtenemos la
suma de los factores pares (2)*(1+3+3 2 ) = 26.
Para eliminar un número impar en un factor par, ignoramos 2 0 , que es 1. Después de este paso, obtener solo factores pares. Tenga en cuenta que 2 es el único primo par.
A continuación se muestra la implementación del enfoque anterior.
C++
// Formula based CPP program to find sum of all
// divisors of n.
#include <bits/stdc++.h>
using namespace std;
// Returns sum of all factors of n.
int sumofFactors(int n)
{
// If n is odd, then there are no even factors.
if (n % 2 != 0)
return 0;
// Traversing through all prime factors.
int res = 1;
for (int i = 2; i <= sqrt(n); i++) {
// While i divides n, print i and divide n
int count = 0, curr_sum = 1, curr_term = 1;
while (n % i == 0) {
count++;
n = n / i;
// here we remove the 2^0 that is 1. All
// other factors
if (i == 2 && count == 1)
curr_sum = 0;
curr_term *= i;
curr_sum += curr_term;
}
res *= curr_sum;
}
// This condition is to handle the case when n
// is a prime number.
if (n >= 2)
res *= (1 + n);
return res;
}
// Driver code
int main()
{
int n = 18;
cout << sumofFactors(n);
return 0;
}
Java
// Formula based Java program to
// find sum of all divisors of n.
import java.util.*;
import java.lang.*;
public class GfG{
// Returns sum of all factors of n.
public static int sumofFactors(int n)
{
// If n is odd, then there
// are no even factors.
if (n % 2 != 0)
return 0;
// Traversing through all prime
// factors.
int res = 1;
for (int i = 2; i <= Math.sqrt(n); i++)
{
int count = 0, curr_sum = 1;
int curr_term = 1;
// While i divides n, print i and
// divide n
while (n % i == 0)
{
count++;
n = n / i;
// here we remove the 2^0 that
// is 1. All other factors
if (i == 2 && count == 1)
curr_sum = 0;
curr_term *= i;
curr_sum += curr_term;
}
res *= curr_sum;
}
// This condition is to handle the
// case when n is a prime number.
if (n >= 2)
res *= (1 + n);
return res;
}
// Driver function
public static void main(String argc[]){
int n = 18;
System.out.println(sumofFactors(n));
}
}
/* This code is contributed by Sagar Shukla */
Python3
# Formula based Python3 # program to find sum # of alldivisors of n. import math # Returns sum of all # factors of n. def sumofFactors(n) : # If n is odd, then # there are no even # factors. if (n % 2 != 0) : return 0 # Traversing through # all prime factors. res = 1 for i in range(2, (int)(math.sqrt(n)) + 1) : # While i divides n # print i and divide n count = 0 curr_sum = 1 curr_term = 1 while (n % i == 0) : count= count + 1 n = n // i # here we remove the # 2^0 that is 1. All # other factors if (i == 2 and count == 1) : curr_sum = 0 curr_term = curr_term * i curr_sum = curr_sum + curr_term res = res * curr_sum # This condition is to # handle the case when # n is a prime number. if (n >= 2) : res = res * (1 + n) return res # Driver code n = 18 print(sumofFactors(n)) # This code is contributed by Nikita Tiwari.
C#
// Formula based C# program to
// find sum of all divisors of n.
using System;
public class GfG {
// Returns sum of all factors of n.
public static int sumofFactors(int n)
{
// If n is odd, then there
// are no even factors.
if (n % 2 != 0)
return 0;
// Traversing through all prime factors.
int res = 1;
for (int i = 2; i <= Math.Sqrt(n); i++)
{
int count = 0, curr_sum = 1;
int curr_term = 1;
// While i divides n, print i
// and divide n
while (n % i == 0)
{
count++;
n = n / i;
// here we remove the 2^0 that
// is 1. All other factors
if (i == 2 && count == 1)
curr_sum = 0;
curr_term *= i;
curr_sum += curr_term;
}
res *= curr_sum;
}
// This condition is to handle the
// case when n is a prime number.
if (n >= 2)
res *= (1 + n);
return res;
}
// Driver Code
public static void Main() {
int n = 18;
Console.WriteLine(sumofFactors(n));
}
}
// This code is contributed by vt_m
PHP
<?php
// Formula based php program to find sum
// of all divisors of n.
// Returns sum of all factors of n.
function sumofFactors($n)
{
// If n is odd, then there are no
// even factors.
if ($n % 2 != 0)
return 0;
// Traversing through all prime factors.
$res = 1;
for ($i = 2; $i <= sqrt($n); $i++) {
// While i divides n, print i
// and divide n
$count = 0;
$curr_sum = 1;
$curr_term = 1;
while ($n % $i == 0) {
$count++;
$n = floor($n / $i);
// here we remove the 2^0
// that is 1. All other
// factors
if ($i == 2 && $count == 1)
$curr_sum = 0;
$curr_term *= $i;
$curr_sum += $curr_term;
}
$res *= $curr_sum;
}
// This condition is to handle the
// case when n is a prime number.
if ($n >= 2)
$res *= (1 + $n);
return $res;
}
// Driver code
$n = 18;
echo sumofFactors($n);
// This code is contributed by mits
?>
Javascript
<script>
// javascript program to
// find sum of all divisors of n.
// Returns sum of all factors of n.
function sumofFactors(n)
{
// If n is odd, then there
// are no even factors.
if (n % 2 != 0)
return 0;
// Traversing through all prime
// factors.
let res = 1;
for (let i = 2; i <= Math.sqrt(n); i++)
{
let count = 0, curr_sum = 1;
let curr_term = 1;
// While i divides n, print i and
// divide n
while (n % i == 0)
{
count++;
n = n / i;
// here we remove the 2^0 that
// is 1. All other factors
if (i == 2 && count == 1)
curr_sum = 0;
curr_term *= i;
curr_sum += curr_term;
}
res *= curr_sum;
}
// This condition is to handle the
// case when n is a prime number.
if (n >= 2)
res *= (1 + n);
return res;
}
// Driver Function
let n = 18;
document.write(sumofFactors(n));
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
26
Complejidad de Tiempo: O(√n log n)
Espacio Auxiliar: O(1)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA