Project Euler
Project Euler probleem 1
Bekijk het originele probleem op Project Euler
We moeten dus de som van alle veelvouden vinden van 3 of 5 onder N waar N = 1000.
De eerste aanpak hiervoor zou een brute force algorithme zijn iets als
Natuurlijk zal dit wel volstaan aangezien we maar alles onder de 1000 moeten controleren.
Maar indien N zeer groot is zal het mogelijks wat langer duren.
Dus we moeten we kijken naar een betere aanpak.
Als je kijkt naar de som van alle veelvouden onder de 1000 van 3
Dan is dat gelijk aan (1 * 3) + (2 * 3) + (3 * 3) + …
Als je goed kijkt zie je dat je 3 kan afzonderen en dat je het dan als volgt kan noteren 3 * ( 1 + 2 + 3 + … )
Voor het gedeelte waar je alle natuurlijke getallen van 1 tot en met N moet opsommen namelijk "( 1 + 2 + 3 + … )" bestaat er een formule.
Meer over de somformule van Gauss
----------------------- | | Som 1 tot en met N = N = | (N * (N + 1) / 2) | | | -----------------------
Het volgende dat je moet weten is wat is N.
In dit geval is N gelijk aan hoeveel veelvouden er onder 1000 zijn voor 3 en 5.
Voor 3 is dat gelijk aan: x = floor(1000 / 3)
Voor 5 is dat gelijk aan: y = floor(1000 / 5)
dus je kan het als volgt herschijven.
-------------------------------------------------- | | Antwoord = | 3 * (x * (x + 1) / 2) + 5 * (y * (y + 1) / 2) | | | --------------------------------------------------
Je moet ook nog rekening houden met getallen die veelvouden van 3 en 5 zijn want nu tel je ze dubbel op. Dus je gaat dat van "antwoord" moeten aftrekken.
Je gaat als eerst de kleinst gemene veelvoud zoeken voor 3 en 5 en dat is gelijk aan 15.
Nu moet je het aantal veelvouden van 15 onder de 1000 moeten zoeken
En dat is gelijk aan: z = floor(1000 / 15)
Nu moet je alleen nog je formule aanpassen voor het juiste antwoord
------------------------------------------------------------------------------ | | Antwoord = | 3 * (x * (x + 1) / 2) + 5 * (y * (y + 1) / 2) - 15 * (z * (z + 1) / 2) | | | ------------------------------------------------------------------------------
Code: