A Project Euler Puzzler (in particolare in PHP)

Question

C'è un'altra domanda recente su Project Euler, ma penso che sia un po 'più specifica (sono davvero interessato solo alle soluzioni basate su PHP), quindi chiedo comunque.

Domanda n. 5 con cui ti occupi: " Qual è il più piccolo numero che è uniformemente divisibile per tutti i numeri da 1 a 20? "

Ora, l'ho risolto due volte. Una volta molto inefficiente e una volta molto più efficiente, ma sono ancora molto lontano da una risposta particolarmente sofisticata (e non sono particolarmente solida in matematica, quindi la mia soluzione di forza bruta). Vedo un paio di aree in cui potrei migliorare questo, ma mi chiedo se qualcuno di voi potrebbe dimostrare una soluzione più efficiente a questo problema.

* spoiler: ecco la mia soluzione non ottimale (7 secondi per l'esecuzione) ma comunque tollerabile (non so cosa fare del doppio $ ... fingi di vedere solo 1 ...

    function euler5(){
        $x = 20;

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

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

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

        }echo $x;
     };

Answer 1

in php sarà simile a questo:

<?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;
}

?>

È almeno due volte più veloce di quello che hai pubblicato.

Answer 2

Raccogli i fattori primi per tutti i numeri tra 1 e 20. Contando gli esponenti massimi di ciascun fattore primo, abbiamo 16 = 2 ** 4 , 9 = 3 ** 2 , oltre a 5, 7, 11, 13, 17, 19 (ciascuno visualizzato una sola volta). Moltiplica il lotto e avrai la tua risposta.

Answer 3

Chris Jester-Young ha ragione.

In generale, se si desidera il numero più piccolo che sia uniformemente divisibile per tutti i numeri da 1 a N, si desidera trovare tutti i numeri primi da 2 a N e, per ognuno, trovare il maggior numero di volte divide qualsiasi numero nell'intervallo. Questo può essere calcolato trovando la massima potenza del numero primo non superiore a N.

Nel caso di 20, come ha sottolineato Chris, 2 ^ 4 è il potere più grande di 2 non maggiore di 20, e 3 ^ 2 è il potere più grande di 3 non maggiore di 20, e solo per tutti gli altri numeri primi il primo potere non è maggiore di 20.

Answer 4

Puoi rimuovere alcuni numeri che sono divisi con, ad esempio 1 non è necessario, tutti i numeri naturali sono divisibili per 1.Non hai nemmeno bisogno di 2, quindi tutti i numeri sono divisibili per multipli di 2 (4 , 8, 16, ecc.) Sono divisibili per 2. Quindi i numeri rilevanti saranno 11, 12, 13, 14, 15, 16, 17, 18 e 19.

Quindi:

<?
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");
}

È la soluzione php più veloce e più breve finora. Circa 1,4 volte più veloce di quello di Czimi sul mio computer. Ma dai un'occhiata alla soluzione Python, è un bel algoritmo.

Answer 6

Alcune persone pensano davvero troppo ...

In Ruby:

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

Answer 7

@Persone che fanno matematica semplice; Non sono sicuro che questo sia l'obiettivo dell'esercizio. Devi imparare nuove lingue e nuovi modi per eseguire cose. Farlo semplicemente con una calcolatrice non è il modo giusto di procedere.

E so che questo è un post in una vecchia vecchia discussione, ma risulta ancora nei risultati di Google :)

Fallo nel codice (ovvero PHP) ho trovato questa la soluzione più veloce:

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ì, è un pezzo modificato dal CMS. Il motivo principale per cui è più veloce è perché quando leggi la domanda, affermano già che il numero più basso possibile per i primi 10 numeri interi è 2520. Pertanto, puoi semplicemente incrementare di 2520 invece di 20. Con conseguente 126 volte meno cicli

Answer 8

So che hai detto PHP, ma ecco la mia bozza approssimativa in 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)

Non è elegante come avrei potuto farlo, ma calcola il multiplo meno comune dei numeri da 2 a 2000 in .15s. Se la tua soluzione iterativa potesse elaborare un miliardo di candidati al secondo, occorrerebbero 10 ^ 849 anni per terminare.

In altre parole, non preoccuparti di ottimizzare l'algoritmo sbagliato.