Dados dos números A y B, la tarea es encontrar la suma de los factores comunes de dos números A y B. Los números A y B son menores que 10^8.
Ejemplos:
Input: A = 10, B = 15 Output: Sum = 6 The common factors are 1, 5, so their sum is 6 Input: A = 100, B = 150 Output: Sum = 93
Enfoque ingenuo: iterar desde i = 1 hasta el mínimo de A y B y comprobar si i es un factor tanto de A como de B. Si i es un factor de A y B , súmalo a la suma. Muestra la suma al final del bucle.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// print the sum of common factors
int sum(int a, int b)
{
// sum of common factors
int sum = 0;
// iterate from 1 to minimum of a and b
for (int i = 1; i <= min(a, b); i++)
// if i is the common factor
// of both the numbers
if (a % i == 0 && b % i == 0)
sum += i;
return sum;
}
// Driver code
int main()
{
int A = 10, B = 15;
// print the sum of common factors
cout << "Sum = " << sum(A, B) << endl;
return 0;
}
Java
// Java implementation of above approach
import java.io.*;
class GFG {
// print the sum of common factors
static int sum(int a, int b)
{
// sum of common factors
int sum = 0;
// iterate from 1 to minimum of a and b
for (int i = 1; i <= Math.min(a, b); i++)
// if i is the common factor
// of both the numbers
if (a % i == 0 && b % i == 0)
sum += i;
return sum;
}
// Driver code
public static void main (String[] args) {
int A = 10, B = 15;
// print the sum of common factors
System.out.print("Sum = " + sum(A, B));
}
}
// This code is contributed by shs..
Python 3
# Python 3 implementation of
# above approach
# print the sum of common factors
def sum(a, b):
# sum of common factors
sum = 0
# iterate from 1 to minimum of a and b
for i in range (1, min(a, b)):
# if i is the common factor
# of both the numbers
if (a % i == 0 and b % i == 0):
sum += i
return sum
# Driver Code
A = 10
B = 15
# print the sum of common factors
print("Sum =", sum(A, B))
# This code is contributed
# by Akanksha Rai
C#
// C# implementation of above approach
using System;
class GFG {
// print the sum of common factors
static int sum(int a, int b)
{
// sum of common factors
int sum = 0;
// iterate from 1 to minimum of a and b
for (int i = 1; i <= Math.Min(a, b); i++)
// if i is the common factor
// of both the numbers
if (a % i == 0 && b % i == 0)
sum += i;
return sum;
}
// Driver code
public static void Main () {
int A = 10, B = 15;
// print the sum of common factors
Console.WriteLine("Sum = " + sum(A, B));
}
}
// This code is contributed by shs..
PHP
<?php
// PHP implementation of above approach
// print the sum of common factors
function sum($a, $b)
{
// sum of common factors
$sum = 0;
// iterate from 1 to minimum of a and b
for ($i = 1; $i <= min($a, $b); $i++)
// if i is the common factor
// of both the numbers
if ($a %$i == 0 && $b %$i == 0)
$sum += $i;
return $sum;
}
// Driver code
$A = 10; $B = 15;
// print the sum of common factors
echo "Sum = " , sum($A, $B);
// This code is contributed by shs.
?>
Javascript
<script>
// Javascript implementation of above approach
// print the sum of common factors
function sum(a, b)
{
// sum of common factors
var sum = 0;
// iterate from 1 to minimum of a and b
for (var i = 1; i <= Math.min(a, b); i++)
// if i is the common factor
// of both the numbers
if (a % i == 0 && b % i == 0)
sum += i;
return sum;
}
var A = 10, B = 15;
// print the sum of common factors
document.write("Sum = " + sum(A, B) + "<br>");
//This code is contributed by SoumikMondal
</script>
Producción:
Sum = 6
Complejidad del tiempo: O(min(a, b))
Espacio Auxiliar: O(1)
Un enfoque eficiente es utilizar el mismo concepto utilizado en Divisores comunes de dos números . Calcula el máximo común divisor (mcd) de dos números dados y luego encuentra la suma de los divisores de ese mcd.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate gcd of two numbers
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to calculate all common divisors
// of two given numbers
// a, b --> input integer numbers
int sumcommDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
// Find the sum of divisors of n.
int sum = 0;
for (int i = 1; i <= sqrt(n); i++) {
// if 'i' is factor of n
if (n % i == 0) {
// check if divisors are equal
if (n / i == i)
sum += i;
else
sum += (n / i) + i;
}
}
return sum;
}
// Driver program to run the case
int main()
{
int a = 10, b = 15;
cout << "Sum = " << sumcommDiv(a, b);
return 0;
}
Java
//Java implementation of above approach
import java.io.*;
class GFG {
// Function to calculate gcd of two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to calculate all common divisors
// of two given numbers
// a, b --> input integer numbers
static int sumcommDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
// Find the sum of divisors of n.
int sum = 0;
for (int i = 1; i <= Math.sqrt(n); i++) {
// if 'i' is factor of n
if (n % i == 0) {
// check if divisors are equal
if (n / i == i)
sum += i;
else
sum += (n / i) + i;
}
}
return sum;
}
// Driver program to run the case
public static void main (String[] args) {
int a = 10, b = 15;
System.out.println("Sum = " + sumcommDiv(a, b));
}
}
Python3
# Python 3 implementation of above approach
from math import gcd,sqrt
# Function to calculate all common divisors
# of two given numbers
# a, b --> input integer numbers
def sumcommDiv(a, b):
# find gcd of a, b
n = gcd(a, b)
# Find the sum of divisors of n.
sum = 0
N = int(sqrt(n))+1
for i in range(1,N,1):
# if 'i' is factor of n
if (n % i == 0):
# check if divisors are equal
if (n / i == i):
sum += i
else:
sum += (n / i) + i
return sum
# Driver program to run the case
if __name__ == '__main__':
a = 10
b = 15
print("Sum =",int(sumcommDiv(a, b)))
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of above approach
using System;
public class GFG{
// Function to calculate gcd of two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to calculate all common divisors
// of two given numbers
// a, b --> input integer numbers
static int sumcommDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
// Find the sum of divisors of n.
int sum = 0;
for (int i = 1; i <= Math.Sqrt(n); i++) {
// if 'i' is factor of n
if (n % i == 0) {
// check if divisors are equal
if (n / i == i)
sum += i;
else
sum += (n / i) + i;
}
}
return sum;
}
// Driver program to run the case
static public void Main (){
int a = 10, b = 15;
Console.WriteLine("Sum = " + sumcommDiv(a, b));
}
}
PHP
<?php
// PHP implementation of above approach
// Function to calculate gcd of two numbers
function gcd($a, $b)
{
if ($a == 0)
return $b;
return gcd($b % $a, $a);
}
// Function to calculate all common divisors
// of two given numbers
// a, b --> input integer numbers
function sumcommDiv($a, $b)
{
// find gcd of a, b
$n = gcd($a, $b);
// Find the sum of divisors of n.
$sum = 0;
for ($i = 1; $i <= sqrt($n); $i++) {
// if 'i' is factor of n
if ($n % $i == 0) {
// check if divisors are equal
if ($n / $i == $i)
$sum += $i;
else
$sum += ($n / $i) + $i;
}
}
return $sum;
}
// Driver program to run the case
$a = 10;
$b = 15;
echo "Sum = " , sumcommDiv($a, $b);
?>
Javascript
<script>
// Javascript implementation of above approach
// Function to calculate gcd of two numbers
function gcd(a, b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to calculate all common divisors
// of two given numbers
// a, b --> input integer numbers
function sumcommDiv(a, b)
{
// find gcd of a, b
var n = gcd(a, b);
// Find the sum of divisors of n.
var sum = 0;
for (var i = 1; i <= Math.sqrt(n); i++) {
// if 'i' is factor of n
if (n % i == 0) {
// check if divisors are equal
if (n / i == i)
sum += i;
else
sum += (n / i) + i;
}
}
return sum;
}
// Driver program to run the case
var a = 10, b = 15;
document.write( "Sum = " + sumcommDiv(a, b));
// This code is contributed by rutvik_56.
</script>
Producción:
Sum = 6
Complejidad del tiempo: O(sqrt(n))
Espacio auxiliar: O (logn)
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA