Cálculo del Máximo Común Divisor y del mínimo común múltiplo

 En bastantes problemas no encontramos con la necesidad de calcular este valor, el MCD sobre todo se usa en criptografía.

Para el MCD  de dos números se no enseña en la escuela que hay que descomponerlos en factores primos y el producto de los factores comunes es el valor del MCD, por ejemplo el MCD de 48 y de 60, su descomposición en factores primos es :

• Para 60 es 2^2 x 5 x 3
• Para 48 es 2^4 x 3

Es el MCD es 2^2 x 3 = 12

Hay otro método menos costoso computacionalmente que es el siguiente:

• Se divide el mayor (dividendo) entre el menor(divisor), si el resto es 0 el MCD es el valor menor
• En caso contrario se divide el divisor entre el resto en un proceso iterativo, en el que se actualizan los valores en cada operación, finaliza cuando  el resto es 0, en este caso el MCD es el último divisor usado.

En este enlace se explica de forma gráfica y fácil

Cálculo de MDC

Para el cálculo del mínimo común múltiplo la operación es sencilla

mcm=(numero1 x numero2)/MCD(numero1,numero2)

A continuación os pongo un código en Java, que he probado en bastantes  casos y no me ha dado error, pero que hay que sestearlos más.

// cálculo de Máxomo común divisor y el mínimo común múltiplo

import java.util.Scanner;

import java.lang.Math;

public class MCD_mcm {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

long numero1;

long numero2;

long resto;

long mayor;

long menor;

// entrada de datos

System.out.println("Introducir el numero 1 ");

numero1=sc.nextLong();

System.out.println("Introducir el mumero 2 ");

numero2=sc.nextLong();

// ordenacion de los numeros

if(numero1>=numero2){

mayor=numero1;

menor=numero2;

}

else{

mayor=numero2;

menor=numero1;

}

// cálculos

resto=mayor % menor; // cálculo del resto

System.out.println("Valor del resto "+resto);

while(resto!=0){

mayor=menor;

menor=resto;

resto=mayor%menor;

}

//Salida del Máximo Común divisor MCD

System.out.printf("El MCD de %d y %d es %d%n",numero1,numero2,menor);

/ calculo de mínimo común multiplo mcm

System.out.printf("El mcm de %d y %d es %d%n",numero1,numero2,Math.abs(numero1*numero2)/menor);

sc.close(); // cerramos el Scanner

}

}

El problema de dado un número entero, encontrar otro entero que sumado al anterior sea divisible por otro entero determinado

 En este caso resolvemos el problema suponiendo que la suma es divisible por 7 y después lo extendemos al resto de los enteros.

Tomemos por ejemplo el número 30 y queremos encontrar otro entero que sumado al anterior sea dicha suma múltiplo de 7, y además le añadimos que sea la menor suma que cumple esta condición.

la lista de los primeros  múltiplos de 7 son:

• 7, 21, 28, 35, 42, 49, 56, etc

Entonces el 30 se encuentra entre el 28 y 35, por lo que el número múltiplo de 7 más cercano es el 35 y el  valor que le tenemos que sumar a 30 es  35-30=5.

Se puede extrapolar a cualquier divisor no solo el 7.

Abajo dejo el código en Java para cualquier divisor :

import java.util.Scanner;

public class Divisible {

    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);

        int numero;

        int divisor;

        int paso;

        // entrada de datos

        System.out.println("Introducir el mumero divisor ");

        divisor=sc.nextInt();             

        

        System.out.println("Introducir el mumero base a sumar ");

        numero=sc.nextInt();

        paso=divisor*(numero/divisor+1);

        // cálculo y resultados

        System.out.printf("Hay que sumar %d a %d para obtener un multiplo de %d que es %d%n",paso-numero,numero,divisor,paso);

        sc.close(); // cerramos el Scanner

    }

    

}

no incluye condicionales, ni búsquedas por bucle que sería la primera tentación para resolver el problema.