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
Prerrequisito : Suma de todos los factores de un número
Como se discutió en la publicación anterior mencionada anteriormente , la suma de los factores de un número es 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.*;
import java.math.*;
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[])
throws IOException
{
int n = 30;
System.out.println(sumofoddFactors(n));
}
}
/* This code is contributed by Nikita Tiwari.*/
Python3
# Formula based Python3 program # to find sum of all divisors # of n. import math # Returns sum of all factors # of n. def sumofoddFactors( n ): # Traversing through all # prime factors. res = 1 # ignore even factors by # of 2 while n % 2 == 0: n = n // 2 for i in range(3, 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+=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(sumofoddFactors(n)) # This code is contributed by "Sharad_Bhardwaj".
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(String[] argc)
{
int n = 30;
Console.Write(sumofoddFactors(n));
}
}
/* This code is contributed by parashar...*/
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 = $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 nitin mittal.
?>
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.
let res = 1;
// ignore even factors by
// removing all powers of
// 2
while (n % 2 == 0)
n = n / 2;
for (let i = 3; i <= Math.sqrt(n); i++)
{
// While i divides n, print
// i and divide n
let count = 0;
let curr_sum = 1;
let 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
let n = 30;
document.write(sumofoddFactors(n));
// This code is contributed by _saurabh_jaiswal
</script>
Producción :
24
Complejidad del tiempo : O(sqrt(n))
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA