matematikk.net

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.
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.

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.