Skip to content

El mayor máximo común divisor

by en 24/03/2014

¡Hola, mentes inquietas!

Inicio de semana y estreno de acertijo. Esta vez vamos a hablar del máximo común divisor, o MCD. Como muchos sabréis, el MCD de dos números A y B es el mayor número que divide simultáneamente a ambos números, A y B. Os ponemos varios ejemplos:

  • MCD(8, 4) = 4
  • MCD(8, 6) = 2
  • MCD(9, 5) = 1

Seguro que recuerdas la forma de calcularlo: si descompones los números en factores primos, el MCD son aquellos comunes elevados al menor exponente. Para programarlo, es mucho más fácil y rápido usar el algoritmo de Euclides.

Si se calcula el MCD de todas las parejas que se forman con los números (distintos) entre 1 y 5 sale la siguiente tabla:

1 2 3 4 5
1
2 1
3 1 1
4 1 2 1
5 1 1 1 1

Se ve que el mayor MCD de todos tiene el valor 2. ¿Cuál es el mayor MCD de todas las parejas que se pueden formar con los números de 1 a 10? ¿Y de 1 a 100? ¿Y a 99999?

Como siempre, si das con la solución y la programas, puedes probarla aquí.

¡Hasta el domingo!

Anuncios

From → Fáciles, Problemas

One Comment
  1. Ivan León permalink

    Hola.
    No se si será la respuesta que se busca pero por lo que yo he entendido creo que es así:
    creo que la solución es la potencia de dos más cercana al número.ejemplo:
    — 5 la potencia más cercana es 4 =2^2 por lo tanto es 2
    — 10 la potencia de dos más cercana es 8 = 2^3 por lo tanto es 3
    — 100 la potencia de dos más cercana es 64 = 2^6 : salida = 6
    etc..
    Esto se debe a que número primo que más potencia tiene entre cualquier número es el “dos”.
    La programación es muy simple:
    class MuchoPorProgramar {
    public static void main(String[] args) {
    Scanner a = new Scanner(System.in);
    int aux = Integer.parseInt(a.nextLine());
    for(int i =0;i<aux;i++){
    long lo = Long.parseLong(a.nextLine());
    for(int j =1;j<63;j++){
    if(lo<Math.pow(2,j)){
    System.out.println(j-1);
    break;
    }
    }
    }
    }

    }

    pongo como límite 63 porque los números serían hasta 10^18, si no fueraeste número el másximo se soluciona con un while hasta el límite de un entero.
    Espero que sea así.
    Un saludo
    Iván León

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: