Un Proyecto Euler Puzzler (específicamente en PHP)

Question

Hay otra pregunta reciente del Proyecto Euler, pero creo que esto es un poco más específico (solo estoy realmente interesado en las soluciones basadas en PHP), así que lo pregunto de todos modos.

Pregunta # 5 le asigna tareas: " ¿Cuál es el más pequeño? número que es divisible por todos los números del 1 al 20? "

Ahora, lo he resuelto dos veces. Una vez muy ineficiente y una vez mucho más eficiente, pero todavía estoy lejos de una respuesta especialmente sofisticada (y no soy especialmente sólido en matemáticas, de ahí mi solución de fuerza bruta). Puedo ver un par de áreas donde podría mejorar esto, pero me pregunto si alguno de ustedes podría demostrar una solución más eficiente a este problema.

* spoiler: Aquí está mi solución menos que óptima (7 segundos para ejecutarse) pero aún tolerable (no estoy seguro de qué hacer con el doble $ ... solo finja que solo ve 1 ...

    function euler5(){
        $x = 20;

        for ($y = 1; $y < 20; $y++) {

            if (!($x%$y)) {

            } else {  
                $x+=20;
                $y = 1;  
            }   

        }echo $x;
     };

Answer 1

en php se verá así:

<?php
function gcd($a,$b) {
    while($a>0 && $b>0) {
        if($a>$b) $a=$a-$b; else $b=$b-$a;        
    }
    if($a==0) return $b;
    return $a;
}
function euler5($i=20) {
    $euler=$x=1;
    while($x++<$i) {
        $euler*=$x/gcd($euler,$x);
    }
    return $euler;
}

?>

Es al menos dos veces más rápido que lo que publicaste.

Answer 2

Recoge factores primos para todos los números entre 1 y 20. Contando los máximos exponentes de cada factor primo, tenemos 16 = 2 ** 4 , 9 = 3 ** 2 , así como 5, 7, 11, 13, 17, 19 (cada uno aparece solo una vez). Multiplique el lote y tendrá su respuesta.

Answer 3

Chris Jester-Young tiene razón.

En general, si desea el número más pequeño que es divisible por todos los números del 1 al N, desearía encontrar todos los números primos del 2 al N, y para cada uno, encontrar el mayor número de veces divide cualquier número en el rango. Esto se puede calcular encontrando la mayor potencia del primo que no sea mayor que N.

En el caso de 20, como señaló Chris, 2 ^ 4 es la mayor potencia de 2 no mayor que 20, y 3 ^ 2 es la mayor potencia de 3 no mayor que 20, y para todos los demás números primos, solo el primer poder no es mayor que 20.

Answer 4

Puede eliminar algunos números que se dividen con, por ejemplo, 1 es innecesario, todos los números naturales son divisibles por 1. No necesita 2 tampoco, y por lo tanto, todos los números son divisibles por múltiplos de 2 (4 , 8, 16, etc.) son divisibles por 2, también. Entonces los números relevantes serán 11, 12, 13, 14, 15, 16, 17, 18 y 19.

Entonces:

<?
function eulerPuzzle()
{
  $integers = array( 11,12,13,14,15,16,17,18,19 );

  for ($n = 20; 1; $n += 20 ) {
    foreach ($integers as $int) { 
      if ( $n % $int ) { 
    break; 
      }
      if ( $int == 19 ) { 
    die ("Result:" . $n); 
      }
    }
  }
}

eulerPuzzle();
?>

Answer 5

<?php
$i=20;
while ($i+=20) {
    for ($j=19;$j!==10;--$j){
        if ($i%$j) continue 2;
    }
    die ("result: $i\n");
}

Es la solución php más rápida y corta hasta ahora. Aproximadamente 1.4 veces más rápido que Czimi en mi comp. Pero echa un vistazo a la solución de Python, eso es un buen algo.

Answer 6

Algunas personas realmente piensan demasiado en esto ...

En Ruby:

puts 5*7*9*11*13*16*17*19

Answer 7

@Personas que hacen matemática simple; No estoy seguro de si ese es el objetivo del ejercicio. Debes aprender nuevos idiomas y nuevas formas de realizar cosas. Simplemente hacerlo con una calculadora no es la forma correcta de hacer las cosas.

Y sé que esta es una publicación en un viejo hilo antiguo pero aún aparece en los resultados de Google :)

Haciéndolo en código (es decir, PHP) descubrí que esta es la solución más rápida:

function eulerPuzzle() {
    $integers = array (11, 12, 13, 14, 15, 16, 17, 18, 19 );

    for($n = 2520; 1; $n += 2520) {
        foreach ( $integers as $int ) {
            if ($n % $int) {
                break;
            }
            if ($int == 19) {
                die ( "Result:" . $n );
            }
        }
    }
}

eulerPuzzle ();

Sí, es una pieza modificada de CMS. La razón principal por la que es más rápido es porque cuando lees la pregunta, ya indican que el número más bajo posible para los primeros 10 enteros es 2520. Por lo tanto, puedes incrementar en 2520 en lugar de 20. resultando 126 veces menos bucles

Answer 8

Sé que dijiste PHP, pero aquí está mi borrador en Python.

#!/usr/bin/env python

from operator import mul

def factor(n):
    factors = {}
    i = 2
    while i < n and n != 1:
        while n % i == 0:
            try:
                factors[i] += 1
            except KeyError:
                factors[i] = 1
            n = n / i
        i += 1
    if n != 1:
        factors[n] = 1
    return factors

base = {}
for i in range(2, 2000):
    for f, n in factor(i).items():
        try:
            base[f] = max(base[f], n)
        except KeyError:
            base[f] = n

print reduce(mul, [f**n for f, n in base.items()], 1)

No es tan elegante como podría haberlo hecho, pero calcula el mínimo común múltiplo de los números del 2 al 2000 en .15s. Si su solución iterativa pudiera procesar mil millones de candidatos por segundo, tardaría 10 ^ 849 años en terminar.

En otras palabras, no te molestes en optimizar el algoritmo incorrecto.