Dado que el primer número para dividir todo (1,2, .., 10) es 2520. Y dado que el primer número para dividir todo (1,2, .., 20) es 232792560. Encuentra el primer número para dividir todo (1,2, .., 100). (todos los números consecutivos del 1 al 100). La respuesta debería ejecutarse en menos de un minuto.

Estoy escribiendo la solución en Java y tengo dos problemas:

  1. ¿Cómo puedo calcular si la solución en sí es un número tan grande que no se puede manejar? Intenté usar "BigInteger" haciendo muchas adiciones y divisiones y no sé si esto está aumentando mi complejidad de tiempo.

  2. ¿Cómo puedo calcular esto en menos de un minuto? La solución que pensé hasta ahora ni siquiera se ha detenido.

Este es mi código Java (usando números enteros grandes):

public static boolean solved(int start, int end, BigInteger answer) {
    for (int i=start; i<=end; i++) {
        if (answer.mod(new BigInteger(valueOf(i))).compareTo(new BigInteger(valueOf(0)))==0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    BigInteger answer = new BigInteger("232792560");
    BigInteger y = new BigInteger("232792560");
    while(!solved(21,100, answer)) {
        answer = answer.add(y);
    }
    System.out.println(answer);
}

Aprovecho que ya conozco la solución para (1, .., 20).

Actualmente simplemente no se detiene.

Pensé que podría mejorarlo cambiando la función solved para verificar solo los valores que nos interesan.

For example:
100 = 25,50,100
99  = 33,99
98 = 49,98
97 = 97
96 = 24,32,48,96

Y así. Pero este simple cálculo de identificar el grupo más pequeño de números necesarios se ha convertido en un problema en sí mismo para el que no busqué / encontré una solución. Por supuesto, la complejidad del tiempo debería permanecer por debajo de un minuto en cualquier caso.

¿Alguna otra idea?

1
ucei 8 dic. 2020 a las 00:35

3 respuestas

La mejor respuesta

El primer número que se puede dividir por todos los elementos de algún conjunto (que es lo que tienes allí, a pesar de la formulación ligeramente diferente) también se conoce como Mínimo común múltiplo de ese conjunto. LCM(a, b, c) = LCM(LCM(a, b), c) y así sucesivamente, por lo que, en general, se puede calcular tomando n - 1 LCM por pares donde n es el número de elementos del conjunto. BigInteger no tiene una función lcm, pero el LCM se puede calcular a través de a * b / gcd(a, b) por lo que en Java con BigInteger:

static BigInteger lcm(BigInteger a, BigInteger b) {
    return a.multiply(b).divide(a.gcd(b));
}

Para 1 a 20, calcular el LCM de esa manera da como resultado 232792560. También es fácil hacerlo hasta 100.

4
harold 7 dic. 2020 a las 21:49

Encuentre todos los poderes primarios máximos en su rango y tome su producto.

P.ej. 1-10: 2 ^ 3, 3 ^ 2, 5 ^ 1, 7 ^ 1: el producto es 2520, que es la respuesta correcta (no 5250). Puede encontrar los números primos a través del tamiz de Eratóstenes o simplemente descargarlos de una lista de números primos.

3
Dave 7 dic. 2020 a las 22:06

Como 100 es pequeño, puede resolverlo produciendo la factorización prima de todos los números del 2 al 100 y manteniendo el mayor exponente de cada prima entre todas las factorizaciones. De hecho, probar divisiones entre 2, 3, 5 y 7 será suficiente para verificar la primalidad hasta 100, y solo hay 25 primos a considerar. Puede implementar un tamiz simple para encontrar los primos y realizar las factorizaciones.

Después de encontrar todos los exponentes de la descomposición prima del mcm, puede dejar esto como la respuesta o realizar las multiplicaciones explícitamente.

1
Yves Daoust 7 dic. 2020 a las 22:20