Ein Projekt Euler Puzzler (speziell in PHP)

Question

Es ist eine weitere aktuelle Projekt Euler Frage, aber ich denke, das ist ein bisschen mehr spezifisch ist (ich bin nur wirklich interessiert in PHP-basierten Lösungen), so frage ich sowieso.

Frage # 5 Aufgaben, die Sie mit: „Was ist die kleinste Zahl das ist teilbar durch alle Zahlen von 1 bis 20? "

Jetzt habe ich es zweimal gelöst. Einmal sehr ineffizient und einmal viel effiziente, aber ich bin noch weit entfernt von einer besonders anspruchsvollen Antwort (und ich bin nicht besonders solide in Mathe daher meine Brute-Force-Lösung). Ich kann ein paar Bereiche sehen, wo ich dies verbessern könnte, aber ich frage mich, ob jemand von euch könnte eine effizientere Lösung für dieses Problem demonstrieren.

* Spoiler: Hier sind meine suboptimal (7 Sekunden zu laufen), aber noch erträglich Lösung (nicht sicher, was ist mit dem Doppel $ zu tun ... nur so tun Sie nur 1 sehen ...

    function euler5(){
        $x = 20;

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

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

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

        }echo $x;
     };

Answer 1

in php es wie folgt aussehen:

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

?>

Die mindestens doppelt so schnell als das, was Sie auf dem Laufenden.

Answer 2

Sammeln Primfaktoren für alle Zahlen zwischen 1 und 20 die maximalen Exponenten eines jeden Primfaktor Zählen, wir haben 16 = 2**4, 9 = 3**2, sowie 5, 7, 11, 13, 17, 19 (jeweils nur einmal erscheinen). Multiplizieren Sie die Menge, und Sie haben Ihre Antwort.

Answer 3

Chris Jester-Young ist richtig.

In der Regel, wenn Sie die kleinste Zahl wollen, die durch alle Zahlen von 1 bis N teilbar ist, würden Sie alle Primzahlen von 2 bis N finden mögen, und für jeden, die größte Anzahl von Zeiten finden sie teilt eine beliebige Zahl im Bereich. Dies kann durch das Finden der größte Macht des Primzahl berechnet werden, die nicht größer als N.

Im Fall von 20, wie Chris darauf hingewiesen, 2 ^ 4 ist die größte Potenz von 2 nicht größer als 20, und 3 ^ 2 ist die größte Leistung von 3 nicht größer als 20 ist, und für alle andere Primzahlen, nur die erste Leistung ist nicht größer als 20.

Answer 4

Sie können einige Zahlen entfernen, die mit geteilt werden, zum Beispiel 1 nicht notwendig ist, alle natürlichen Zahlen, die durch 1.you teilbar sind nicht 2 entweder brauchen, und deshalb sind alle Zahlen teilbar durch ein Vielfaches von 2 (4, 8 , 16, etc.) durch 2 teilbar, auch. So sind die entsprechenden Zahlen 11 sein, 12, 13, 14, 15, 16, 17, 18 und 19.

So:

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

ist die schnellste und kürzeste PHP-Lösung so weit. Über 1,4x schneller als Czimi auf meinem comp. Aber überprüfen Sie die Python-Lösung aus, das ist eine schöne algo.

Answer 6

Einige Leute wirklich über-denken, dies ...

In Ruby:

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

Answer 7

@People einfache mathematische tun; Ich bin mir nicht sicher, ob das Ziel der Übung ist. Sie sind auf neue Sprachen und neue Wege zu lernen, Sachen durchzuführen. Tun Sie es einfach von einem Rechner ist nicht der richtige Weg, um Dinge geht.

Und ich weiß, dass dies ein Beitrag in einem alten alten Thread, aber es kommt immer noch in Google-Ergebnissen auf:)

es im Code tun (PHP, das ist) Ich fand dies die schnellste Lösung sein:

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 ();

Ja, es ist ein modifiziertes Stück von CMS. Der Hauptgrund ist es schneller ist, weil, wenn Sie die Frage zu lesen, geben sie bereits, dass die geringstmögliche Zahl für die ersten 10 ganzen Zahlen ist 2520 dafür, können Sie einfach von 2.520 erhöht statt 20 in 126-mal weniger Schleifen resultierenden

Answer 8

Ich weiß, Sie sagten PHP, aber hier ist mein Rohentwurf 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)

Es ist nicht so elegant, wie ich es hätte machen können, aber es berechnet die kleinste gemeinsame Vielfache der Zahlen von 2 bis 2000 in .15s. Wenn Ihr iterative Lösung eine Milliarde Kandidaten pro Sekunde verarbeiten könnte, wäre es 10 ^ 849 Jahre in Anspruch nehmen.

Mit anderen Worten, nicht der Mühe des falschen Algorithmus optimiert werden.