[Python] Finne minste heltall som er delelig med...

[Zahand]

Hei, jeg holder på med noen oppgaver fra http://projecteuler.net/

I en oppgave skal jeg finne minste heltall som er delelig med all tall fra 1 til k (Gir ingen rest)

For eksempel, dersom k = 15, så vil 360360 være det minste tallet som er delelig med alle tall fra 1 - 15.

Jeg gjorde oppgaven, men min løsning var ganske ineffektiv og brukte veldig lang tid. Så jeg søkte litt på google og fant denne koden.

Code: Select all

def smallest_multiple(k):
    n = 1
    for i in range(1, k + 1):
        for j in range(1, k + 1):
            if (n * j) % i == 0:
                n *= j
                break
    return n

Jeg skjønner koden, men jeg skjønner ikke helt matematikken bak dette. Håper at dere skjønner hva det er jeg prøver å komme frem til

Takk på forhånd.

[Gustav]

Algoritmen starter med å finne det minste positive heltallet som er delelig med 1, altså 1. Variabelen n settes dermed lik 1.

Deretter finner den det minste positive heltallet som også er delelig med 2. Dette gjøres ved å gange n med de positive heltallene fra 1 og oppover og teste for hver iterasjon. For-løkka stopper idet man har funnet det første tallet som er delelig med 2. Deretter oppdateres n, og man står igjen med det minste tallet som er delelig med både 1 og 2.

Håper dette var forståelig.


EDIT: En matematisk forklaring: Dersom n er et tall som er delelig med alle tall 1 til k, så må et tall som er delelig med alle tall 1 til k+1 være et multiplum av n, altså på formen nm for m mellom 1 og k+1.