Dado un número N , la tarea es encontrar dos números a y b tales que a + b = N y MCM(a, b) sea mínimo.
Ejemplos:
Entrada: N = 15
Salida: a = 5, b = 10
Explicación:
El par 5, 10 tiene una suma de 15 y su MCM es 10 que es el mínimo posible.Entrada: N = 4
Salida: a = 2, b = 2
Explicación:
El par 2, 2 tiene una suma de 4 y su MCM es 2 que es el mínimo posible.
Enfoque: La idea es utilizar el concepto de GCD y LCM . A continuación se muestran los pasos:
- Si N es un número primo , la respuesta es 1 y N – 1 porque, en cualquier otro caso, a + b > N o LCM(a, b) es > N – 1 . Esto se debe a que si N es primo, implica que N es impar. Entonces a y b, cualquiera de ellos debe ser impar y el otro par. Por lo tanto, MCM(a, b) debe ser mayor que N (si no es 1 y N – 1) ya que 2 siempre será un factor.
- Si N no es un número primo , elija a, b tal que su GCD sea máximo , debido a la fórmula MCM(a, b) = a*b / GCD (a, b) . Entonces, para minimizar LCM(a, b) debemosmaximizar MCD(a, b).
- Si x es un divisor de N , entonces, mediante matemáticas simples, a y b pueden representarse como N / x y N / x*( x – 1) respectivamente. Ahora como a = N / x y b = N / x * (x – 1) , entonces su MCD resulta como N / x . Para maximizar este GCD, tome la x más pequeña posible o el divisor más pequeño posible de N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if number is
// prime or not
bool prime(int n)
{
// As 1 is neither prime
// nor composite return false
if (n == 1)
return false;
// Check if it is divided by any
// number then it is not prime,
// return false
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
// Check if n is not divided
// by any number then it is
// prime and hence return true
return true;
}
// Function to find the pair (a, b)
// such that sum is N & LCM is minimum
void minDivisor(int n)
{
// Check if the number is prime
if (prime(n)) {
cout << 1 << " " << n - 1;
}
// Now, if it is not prime then
// find the least divisor
else {
for (int i = 2; i * i <= n; i++) {
// Check if divides n then
// it is a factor
if (n % i == 0) {
// Required output is
// a = n/i & b = n/i*(n-1)
cout << n / i << " "
<< n / i * (i - 1);
break;
}
}
}
}
// Driver Code
int main()
{
int N = 4;
// Function call
minDivisor(N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check if number is
// prime or not
static boolean prime(int n)
{
// As 1 is neither prime
// nor composite return false
if (n == 1)
return false;
// Check if it is divided by any
// number then it is not prime,
// return false
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
// Check if n is not divided
// by any number then it is
// prime and hence return true
return true;
}
// Function to find the pair (a, b)
// such that sum is N & LCM is minimum
static void minDivisor(int n)
{
// Check if the number is prime
if (prime(n))
{
System.out.print(1 + " " + (n - 1));
}
// Now, if it is not prime then
// find the least divisor
else
{
for (int i = 2; i * i <= n; i++)
{
// Check if divides n then
// it is a factor
if (n % i == 0)
{
// Required output is
// a = n/i & b = n/i*(n-1)
System.out.print(n / i + " " +
(n / i * (i - 1)));
break;
}
}
}
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
// Function call
minDivisor(N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach # Function to check if number is # prime or not def prime(n): # As 1 is neither prime # nor composite return false if (n == 1): return False # Check if it is divided by any # number then it is not prime, # return false for i in range(2, n + 1): if i * i > n: break if (n % i == 0): return False # Check if n is not divided # by any number then it is # prime and hence return true return True # Function to find the pair (a, b) # such that sum is N & LCM is minimum def minDivisor(n): # Check if the number is prime if (prime(n)): print(1, n - 1) # Now, if it is not prime then # find the least divisor else: for i in range(2, n + 1): if i * i > n: break # Check if divides n then # it is a factor if (n % i == 0): # Required output is # a = n/i & b = n/i*(n-1) print(n // i, n // i * (i - 1)) break # Driver Code N = 4 # Function call minDivisor(N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if number is
// prime or not
static bool prime(int n)
{
// As 1 is neither prime
// nor composite return false
if (n == 1)
return false;
// Check if it is divided by any
// number then it is not prime,
// return false
for(int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
// Check if n is not divided
// by any number then it is
// prime and hence return true
return true;
}
// Function to find the pair (a, b)
// such that sum is N & LCM is minimum
static void minDivisor(int n)
{
// Check if the number is prime
if (prime(n))
{
Console.Write(1 + " " + (n - 1));
}
// Now, if it is not prime then
// find the least divisor
else
{
for(int i = 2; i * i <= n; i++)
{
// Check if divides n then
// it is a factor
if (n % i == 0)
{
// Required output is
// a = n/i & b = n/i*(n-1)
Console.Write(n / i + " " +
(n / i * (i - 1)));
break;
}
}
}
}
// Driver Code
public static void Main(String[] args)
{
int N = 4;
// Function call
minDivisor(N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program for the above approach
// Function to check if number is
// prime or not
function prime(n)
{
// As 1 is neither prime
// nor composite return false
if (n == 1)
return false;
// Check if it is divided by any
// number then it is not prime,
// return false
for (i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
// Check if n is not divided
// by any number then it is
// prime and hence return true
return true;
}
// Function to find the pair (a, b)
// such that sum is N & LCM is minimum
function minDivisor(n)
{
// Check if the number is prime
if (prime(n))
{
document.write(1 + " " + (n - 1));
}
// Now, if it is not prime then
// find the least divisor
else
{
for (i = 2; i * i <= n; i++)
{
// Check if divides n then
// it is a factor
if (n % i == 0)
{
// Required output is
// a = n/i & b = n/i*(n-1)
document.write(n / i + " " + (n / i * (i - 1)));
break;
}
}
}
}
// Driver Code
var N = 4;
// Function call
minDivisor(N);
// This code is contributed by todaysgaurav
</script>
Producción:
2 2
Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por tirtharajsen01 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA