Project Euler Aufgabe - Sum of multiples of 3 and 5 below 1000.

Question

Aufgabe (Copy-paste Aus www.projecteuler.net)

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Mein Code: 

#include <iostream>

using namespace std;

int x =0;


int main()
{
 //i starts from zero and increases stepwise to 999.
for(int i = 0; i < 1000; ++i) 
  {

    //Lets filter the right numbers by the condition below. 
    if((i%3==0 && i%5!=0) || (i%5==0 && i%3!=0) || (i%15==0)) 
      x = x + i; // sum the numbers
    
  }

//output the sum. 
cout << "The sum is " << x << "." << endl;

return 0; 
}

https://repl.it/@limonade1234/sumofmultiplesofthreeandfivebelow1000


Frage

Ist die Zahl richtig? Also für 0-10 stimmt sie, das hab ich nachgerechnet.

Wie kann ich aber wissen ob es für alle Zahlen bis 999 stimmt.

Answer 1

Hallo limonade,

Wie kann ich aber wissen ob es für alle Zahlen bis 999 stimmt. 

in diesem Fall kannst Du es auch einfach nachrechnen. Sei \(N(x)=x(x+1)/2\) die Summe der Zahlen von \(1\) bis \(x\), dann ist die gesuchte Summe \(s\): $$\begin{aligned} s &= 3 \cdot N\left( \left\lfloor \frac{999}{3} \right\rfloor \right) + 5 \cdot N\left( \left\lfloor \frac{999}{5} \right\rfloor \right) - 15 \cdot N\left(   \left\lfloor \frac{999}{3 \cdot 5} \right\rfloor \right) \\ &= 3 \cdot N(333) + 5 \cdot N(199) - 15 \cdot N(66) \\ &= 3 \cdot 55611 + 5 \cdot 19900 - 15 \cdot 2211 \\ &= 233168\end{aligned}$$

Comments

Es ist interessant, dass das Programm oben ohne die in der Antwort benutzte Inklusions-Exklusions-Formel auskommt.

Answer 2

Ist die Zahl richtig?

Ja.

Wie kann ich aber wissen ob es für alle Zahlen bis 999 stimmt. 

Hol dir einen Benutzernamen und ein Passwort. Dann kannst du deine Lösungsvorschläge dort eingeben und bekommst gesagt, ob sie richtig sind.

Answer 3

#include <iostream>
using namespace std;
int x =0;
int main() {
  //i starts from zero and increases stepwise to 999.
  for (int i = 0; i < 1000; ++i) {
      //Lets filter the right numbers by this easier condition below. 
      if ( (i%3==0) || (i%5==0 ) )
        x = x + i; // sum the numbers
    }
  //output the sum. 
  cout << "The sum is " << x << "." << endl;
return 0; 
}

Dieser Code verwendet eine einfachere Filterbedingung und liefert das Gleiche.