Rubin. Wie man meine Schleife verbessert, die nach dem kleinsten Vielfachen der Zahlenbereiche sucht

Question

Ich muss mich mit dieser Aufgabe befassen:

"2520 ist die kleinste Zahl, die durch jede der Zahlen von 1 bis 10 ohne jede geteilt werden kann Rest. Was ist die kleinste positive Zahl, die gleichmäßig durch alle Zahlen von 1 bis 20 teilbar ist? "

Meine Lösung sieht wie folgt aus:

all_numbers = [] 

1.upto(2600) do |j| 
    1.upto(10) do |i| 
      if j % i == 0 
       all_numbers << j 
       end 
    end 
end 

result = all_numbers.select{|element| all_numbers.count(element) > 9 } 
p result[0] 

Das gibt mir die richtige Antwort, aber wenn ich für eine Reihe von 0..20 überprüfen möchten und Code wie folgt ändern:

all_numbers = [] 

1.upto(100000) do |j| 
    1.upto(20) do |i| 
      if j % i == 0 
       all_numbers << j 
       end 
    end 
end 

result = all_numbers.select{|element| all_numbers.count(element) > 19 } 
p result[0] 

es dauert zu viel Zeit, um eine Antwort zu erhalten (eigentlich habe ich nicht einmal so lange gewartet ... also hab noch nicht die richtige Antwort ..).

Irgendwelche Ideen? Danke vielmals!

Answer 1

Sie greifen dies aus dem falschen Winkel an. Anstatt zu suchen, bis Sie die richtige Nummer gefunden haben, möchten Sie die Nummer berechnen. Was im Grunde bedeutet, alle Zahlen zu betrachten, dass das Ergebnis teilbar sein muss, indem man ihre Primfaktoren findet und dann die größte Potenz jedes Prims verwendet. Zum Beispiel die erste Zahl zu finden, die durch die Zahlen 1-6 wäre wie diese gleichmäßig teilbar ist:

1: ignore 
2: prime factors 2**1 
3: prime factors 3**1 
4: prime factors 2**2 
5: prime factors 5**1 
6: prime factors 2**1, 3**1 

Also, Ihre einzigartige Primzahlen sind 2, 3 und 5. 2 quadriert wird, ist alles andere die erste Macht. multiplizieren, dass alle zusammen und erhalten Sie 2 * 2 * 3 * 5, die ist 60. es ein klein wenig weiter für 1-10 Fall machen, haben wir:

7: prime factors 7**1 
8: prime factors 2**3 
9: prime factors 3**2 
10: prime factors 2**1, 5**1 

So jetzt Ihre einzigartige Primzahlen ihre größte Macht sind 2**3, 3**2, 5**1, 7**1 Multiplizieren Sie 2 * 2 * 2 * 3 * 3 * 5 * 7, und Sie erhalten 2520. Welche Sie bereits wussten. Wenn Sie diesen Ansatz für die Zahlen 1-20 verwenden, erhalten Sie viel schneller ein Ergebnis als an jeder Zahl.

Ruby hat eine Primzahlbibliothek, wenn Sie diese verwenden dürfen (vorausgesetzt, es handelt sich um eine HW-Zuweisung). Insbesondere die primedivision-Methode wird die Primfaktoren auf sehr hilfreiche Weise für dieses spezielle Problem zurückgeben.