Dados dos números A y B, la tarea es dividir los dos números A y B por sus divisores comunes. Los números A y B son menores que 10^8.
Ejemplos:
Input: A = 10, B = 15 Output: A = 2, B = 3 The common factors are 1, 5 Input: A = 100, B = 150 Output: A = 2, B = 3
Enfoque ingenuo: iterar desde i = 1 hasta el mínimo de A y B y verificar si i es un factor de A y B. Si i es un factor de A y B , divida los dos números A y B por i.
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 numbers after dividing
// them by their common factors
void divide(int a, int b)
{
// iterate from 1 to minimum of a and b
for (int i = 2; i <= min(a, b); i++) {
// if i is the common factor
// of both the numbers
while (a % i == 0 && b % i == 0) {
a = a / i;
b = b / i;
}
}
cout << "A = " << a << ", B = " << b << endl;
}
// Driver code
int main()
{
int A = 10, B = 15;
// divide A and B by their common factors
divide(A, B);
return 0;
}
C
// C implementation of above approach
#include <stdio.h>
// print the numbers after dividing
// them by their common factors
void divide(int a, int b)
{
// iterate from 1 to minimum of a and b
int min;
min = a;
if (min > b)
min = b;
for (int i = 2; i <= min; i++) {
// if i is the common factor
// of both the numbers
while (a % i == 0 && b % i == 0) {
a = a / i;
b = b / i;
}
}
printf("A = %d, B = %d\n", a, b);
}
// Driver code
int main()
{
int A = 10, B = 15;
// divide A and B by their common factors
divide(A, B);
return 0;
}
// This code is contributed by kothvvsakash
Java
// Java implementation of above approach
import java.util.*;
class solution
{
// print the numbers after dividing
// them by their common factors
static void divide(int a, int b)
{
// iterate from 1 to minimum of a and b
for (int i = 2; i <= Math.min(a, b); i++) {
// if i is the common factor
// of both the numbers
while (a % i == 0 && b % i == 0) {
a = a / i;
b = b / i;
}
}
System.out.println("A = "+a+", B = "+b);
}
// Driver code
public static void main(String args[])
{
int A = 10, B = 15;
// divide A and B by their common factors
divide(A, B);
}
}
// This code is contributed by
// Surendra_Gangwar
Python3
# Python3 implementation of above approach
# print the numbers after dividing
# them by their common factors
def divide(a, b) :
# iterate from 1 to minimum of a and b
for i in range(2, min(a, b) + 1) :
# if i is the common factor
# of both the numbers
while (a % i == 0 and b % i == 0) :
a = a // i
b = b // i
print("A =", a, ", B =", b)
# Driver code
if __name__ == "__main__" :
A, B = 10, 15
# divide A and B by their
# common factors
divide(A, B)
# This code is contributed by Ryuga
C#
// C# implementation of above approach
using System;
class GFG
{
// print the numbers after dividing
// them by their common factors
static void divide(int a, int b)
{
// iterate from 1 to minimum of a and b
for (int i = 2; i <= Math.Min(a, b); i++)
{
// if i is the common factor
// of both the numbers
while (a % i == 0 && b % i == 0)
{
a = a / i;
b = b / i;
}
}
Console.WriteLine("A = "+a+", B = "+b);
}
// Driver code
static public void Main ()
{
int A = 10, B = 15;
// divide A and B by their common factors
divide(A, B);
}
}
// This code is contributed by ajit.
PHP
<?php
// PHP implementation of above approach
// print the numbers after dividing
// them by their common factors
function divide($a, $b)
{
// iterate from 1 to minimum of a and b
for ($i = 2; $i <= min($a, $b); $i++)
{
// if i is the common factor
// of both the numbers
while ($a % $i == 0 &&
$b % $i == 0)
{
$a = $a / $i;
$b = $b / $i;
}
}
echo "A = ", $a, ", B = ", $b, "\n";
}
// Driver code
$A = 10;
$B = 15;
// divide A and B by their common factors
divide($A, $B);
// This code is contributed by Sach_Code
?>
Javascript
<script>
// Javascript implementation of above approach
// print the numbers after dividing
// them by their common factors
function divide(a, b)
{
// iterate from 1 to minimum of a and b
for (let i = 2; i <= Math.min(a, b); i++) {
// if i is the common factor
// of both the numbers
while (a % i == 0 && b % i == 0) {
a = a / i;
b = b / i;
}
}
document.write("A = " + a + ", B = " + b + "<br>");
}
// Driver code
let A = 10, B = 15;
// divide A and B by their common factors
divide(A, B);
// This code is contributed by Mayank Tyagi
</script>
Producción:
A = 2, B = 3
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 divide los números por su 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
void commDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
a = a / n;
b = b / n;
cout << "A = " << a << ", B = " << b << endl;
}
// Driver code
int main()
{
int a = 10, b = 15;
commDiv(a, b);
return 0;
}
C
// C implementation of above approach
#include <stdio.h>
// 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
void commDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
a = a / n;
b = b / n;
printf("A = %d, B = %d\n",a,b);
}
// Driver code
int main()
{
int a = 10, b = 15;
commDiv(a, b);
return 0;
}
// This code is contributed by kothvvsaakash
Java
// Java implementation of above approach
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 void commDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
a = a / n;
b = b / n;
System.out.println("A = " + a +
", B = " + b);
}
// Driver code
public static void main(String[] args)
{
int a = 10, b = 15;
commDiv(a, b);
}
}
// This code is contributed
// by Code_Mech
Python3
# Python3 implementation of above approach
# Function to calculate gcd of two numbers
def 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 eger numbers
def commDiv(a, b):
# find gcd of a, b
n = gcd(a, b)
a = a // n
b = b // n
print("A =", a, ", B =", b)
# Driver code
a, b = 10, 15
commDiv(a, b)
# This code is contributed
# by mohit kumar
C#
// C# implementation of above approach
using System;
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 void commDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
a = a / n;
b = b / n;
Console.WriteLine("A = " + a +
", B = " + b);
}
// Driver code
public static void Main()
{
int a = 10, b = 15;
commDiv(a, b);
}
}
// This code is contributed
// by Code_Mech
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 commDiv($a, $b)
{
// find gcd of a, b
$n = gcd($a, $b);
$a = (int)($a / $n);
$b = (int)($b / $n);
echo "A = " . $a .
", B = " . $b . "\n";
}
// Driver code
$a = 10;
$b = 15;
commDiv($a, $b);
// This code is contributed by mits
?>
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 commDiv(a, b)
{
// find gcd of a, b
let n = gcd(a, b);
a = parseInt(a / n, 10);
b = parseInt(b / n, 10);
document.write("A = " + a + ", B = " + b);
}
let a = 10, b = 15;
commDiv(a, b);
</script>
Producción:
A = 2, B = 3
Complejidad del tiempo: O(log(min(a, b)))
Espacio auxiliar: O(log(min(a, b)))
Publicación traducida automáticamente
Artículo escrito por gfg_sal_gfg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA