Dado un número n, la tarea es encontrar la suma de factores impares.
Ejemplos:
Input : n = 30 Output : 24 Odd dividers sum 1 + 3 + 5 + 15 = 24 Input : 18 Output : 13 Odd dividers sum 1 + 3 + 9 = 13
Sean p 1 , p 2 , … p k factores primos de n. Sean a 1 , a 2 , .. a k potencias máximas de p 1 , p 2 , .. p k respectivamente que dividen n, es decir, podemos escribir n como n = (p 1 a 1 )*(p 2 a 2 )* … (p k a k ) .
Sum of divisors = (1 + p1 + p12 ... p1a1) *
(1 + p2 + p22 ... p2a2) *
.............................................
(1 + pk + pk2 ... pkak)
Para encontrar la suma de los factores impares, simplemente debemos ignorar los factores pares y sus poderes. Por ejemplo, considere n = 18. Se puede escribir como 2 1 3 2 y el sol de todos los factores es (1)*(1 + 2)*(1 + 3 + 3 2 ). Suma de factores impares (1)*(1+3+3 2 ) = 13.
Para eliminar todos los factores pares, dividimos repetidamente n mientras sea divisible por 2. Después de este paso, solo obtenemos factores impares. Tenga en cuenta que 2 es el único primo par.
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 sumofoddFactors(int n)
{
// Traversing through all
// prime factors.
int res = 1;
// ignore even factors by
// removing all powers of
// 2
while (n % 2 == 0)
n = n / 2;
for (int i = 3; i <= sqrt(n); i++)
{
// While i divides n, print
// i and divide n
int count = 0, curr_sum = 1
int curr_term = 1;
while (n % i == 0) {
count++;
n = n / i;
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 = 30;
cout << sumofoddFactors(n);
return 0;
}
Java
// Formula based Java program
// to find sum of all
// divisors of n.
import java.io.*;
class GFG
{
// Returns sum of all factors of n.
static int sumofoddFactors(int n)
{
// Traversing through all
// prime factors.
int res = 1;
// ignore even factors by
// removing all powers of
// 2
while (n % 2 == 0)
n = n / 2;
for (int i = 3; i <= Math. sqrt(n); i++)
{
// While i divides n, print
// i and divide n
int count = 0, curr_sum = 1;
int curr_term = 1;
while (n % i == 0)
{
count++;
n = n / i;
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 (String[] args) {
int n = 30;
System.out.println ( sumofoddFactors(n));
}
}
// This code is contributed by vt_m.
Python 3
# Formula based Python 3 program # to find sum of all divisors of n # Returns sum of all factors of n import math def sumofoddFactors(n): # Traversing through all prime factors res = 1 # ignore even factors by # removing all powers of 2 while (n % 2) == 0 : n = n / 2 i=3 while i <= math.sqrt(n): # While i divides n, print # i and divide n count = 0 curr_sum = 1 curr_term = 1 while (n % i) == 0: count += 1 n = n / i 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 = 30 print(int(sumofoddFactors(n))) # This code is contributed # by Azkia Anam.
C#
// Formula based C# program
// to find sum of all
// divisors of n.
using System;
class GFG
{
// Returns sum of all factors of n.
static int sumofoddFactors(int n)
{
// Traversing through all
// prime factors.
int res = 1;
// ignore even factors by
// removing all powers of
// 2
while (n % 2 == 0)
n = n / 2;
for (int i = 3; i <= Math. Sqrt(n); i++)
{
// While i divides n, print
// i and divide n
int count = 0, curr_sum = 1;
int curr_term = 1;
while (n % i == 0)
{
count++;
n = n / i;
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 = 30;
Console.WriteLine( sumofoddFactors(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 sumofoddFactors($n)
{
// Traversing through all
// prime factors.
$res = 1;
// ignore even factors by removing
// all powers of 2
while ($n % 2 == 0)
$n = $n / 2;
for ($i = 3; $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 = (int) $n / $i;
$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 = 30;
echo sumofoddFactors($n);
// This code is contributed
// by Sach_Code
?>
Javascript
<script>
// Formula based javascript program
// to find sum of all
// divisors of n.
// Returns sum of all factors of n.
function sumofoddFactors(n)
{
// Traversing through all
// prime factors.
var res = 1;
// ignore even factors by
// removing all powers of
// 2
while (n % 2 == 0)
n = n / 2;
for (var i = 3; i <= Math.sqrt(n); i++) {
// While i divides n, print
// i and divide n
var count = 0, curr_sum = 1;
var curr_term = 1;
while (n % i == 0) {
count++;
n = n / i;
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
var n = 30;
document.write(sumofoddFactors(n));
// This code is contributed by gauravrajput1
</script>
Producción:
24
Complejidad de tiempo: O (n 1/2 )
Espacio auxiliar: O(1)
Consulte el artículo completo sobre Encontrar la suma de los factores impares de un número para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA