C++

Forum

 
Project Euler

Skoliro (2)
Hello! I was working on the first project Euler problem which is:

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.

The solution I came up with was to use a for loop to slowly work through the multiples and test whether or not it was below 1000. If it was the for loop would run again and if not it would end and move to the next set of multiples, slowly adding them together. I came up with this code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
  #include "Header.h"


int main() {

	int a = 1;
	int b = 0;
	int c = 0;

	for (int test = 0; test = 0;a = a + 1) {

		b = a * 3;

		if (b < 1000) {
			c = c + b;
		} else {
			test = 1;
		}
	}

	cout << c;

	int random;

	cin >> random;

	return 0;


}


My header file only includes a #include <iostream> and using namespace std;. So I know the problem is not there. For some reason when I run the program, however, it only returns 0 and nothing else. I've tried rewriting some of the functions in different ways but I'm probably just missing something blatantly obvious. Maybe one of you find people could help?
edge6768 (124)
The conditional in your for loop test = 0 should be test == 0 =P

I also think it would be easier to follow the code in a do...while(conditional) loop - something like:
1
2
3
4
5
 
	do {
		b = a * 3;
		c += b;
		a++;
	} while(b < 1000);


Apologies, that causes a one-off error! Correct code would be:
1
2
3
4
5
 
do {
c += b;
b = a * 3;
a++;
} while(b < 1000);
Last edited on
Skoliro (2)
Thank you so much! That makes so much sense! I completely overlooked the do while loop format. That would simplify the code so much.
Arslan7041 (753)
Why don't you run the for loop from 0 to 1000, and for every multiple of 3 or 5, add it to a running sum?
lastchance (6980)
I can't see any check for being a multiple of 5 in your code. You are just adding multiples of 3.


To really overcomplicate it, but if you want your code to run really fast and all you want is the sum, you strictly only need to check up to 3*5 = 15 (plus a few left over at the end). The numbers will repeat modulo 3*5 and you could find how many times this went into 1000-1.

3 + 5 + 6 + 9 + 10 + 12 + 15 = 60, from 7 numbers, so, repeating every 15:
18 + 20 + 21 + 24 + 25 + 27 + 30 = 60 + 7 * 15
33 + 35 + 36 + 39 + 40 + 42 + 45 = 60 + 7 * ( 2 * 15 )
etc


Alternatively, and provided your numbers are coprime (as they are here, but not in general):
- add up the multiples of 3 (use the formula for an arithmetic series rather than looping)
- plus add up the multiples of 5 (ditto)
- minus sum of the multiples of 3*5 = 15 (to avoid double counting)

Gets more complicated if the numbers aren't coprime, but you divide out the HCF from one of them first and get the right result.
Last edited on
gunnerfunner (2127)
Find the sum of all the multiples of 3 or 5 below 1000


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include<iostream>
using namespace std;

bool multiple(int n);

int main()
{
    int sum = 0;

    for (int i = 0; i < 1000; i++)
    {
        if(multiple(i))
        {
            sum += i;
        }
    }
    cout<<sum;
}
bool multiple (int n)
{
    return ((n%3 == 0) || (n%5 == 0));
}
lastchance (6980)
See https://en.wikipedia.org/wiki/Project_Euler

Looping is a VERY inefficient way to do it.

Input 3 5 1000 in response to code below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include<iostream>
using namespace std;

int sumMultiples( int n, int nMax )         // function to find sum of multiples of n less than OR EQUAL TO nMax
{
   int num   = nMax / n;                    // number of whole-number multiples
   int first = n;                           // first term of arithmetic series
   int last  = num * n;                     // last term of arithmetic series
   return num * ( first + last ) / 2;       // sum of arithmetic series (at least one factor is even; integer division not a problem)
}

int main()
{
   int m, n, big;
   cout << "You will determine the sum of multiples of m and n that are (STRICTLY) less than big" << endl;
   cout << "Make sure that m and n are coprime (have no common factors)" << endl;
   cout << "Input m, n, big: ";
   cin >> m >> n >> big;
   cout << "\nSum is " << sumMultiples( m, big - 1 ) + sumMultiples( n, big - 1 ) - sumMultiples( m * n, big - 1 ) << endl;
}
Last edited on
JLBorges (13770)
Here are some measurements:
Note: The code posted by lastchance is rewritten to be evaluated at compile-time
(m*n instead of lcm(m,n) works only if m and n are relatively prime; here lcm(3,5) == 3*5).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
#include <iostream>
#include <algorithm>
#include <ctime>

struct cpu_timer
{
    ~cpu_timer()
    {
        const auto finish = std::clock() ;
        std::cout << (finish-start) * 1000.0 / CLOCKS_PER_SEC << " millisecs (processor)\n" ;
    };

    private: std::clock_t start = std::clock() ;
};


int main()
{
    constexpr long long UBOUND = 400'000'000 ; // numbers less than this

    {
        std::cout << "one loop with an if (logical or in condition):\n" ;
        long long sum = 0 ;

        {
            cpu_timer timer ;

            for( long long n = 1 ; n < UBOUND ; ++n ) // for every number from 1 to UBOUND-1
            {
                if( n%3 == 0 || n%5 == 0 ) sum += n ; // multiple of three or five (or both)
            }
        }
        std::cout << "sum == " << sum <<       "\n---------------------\n\n" ; ;
    }

    {
        std::cout << "one loop with if - else if construct:\n" ;
        long long sum = 0 ;

        {
            cpu_timer timer ;

            for( long long n = 1 ; n < UBOUND ; ++n ) // for every number from 1 to UBOUND-1
            {
                if( n%3 == 0 ) sum += n ;
                else if( n%5 == 0 ) sum += n ; // else if: we don't want to add multiples of 15 twice
            }
        }
        std::cout << "sum == " << sum <<       "\n---------------------\n\n" ; ;
    }

    {
        std::cout << "three loops: simple, transparent code; no conditionals in the loops)\n"
                     "(the optimiser can figure out everything about what is going on):\n" ;
        long long sum = 0 ;

        {
            cpu_timer timer ;

            for( long long n = 3 ; n < UBOUND ; n += 3 ) sum += n ; // all multiples of three
            for( long long n = 5 ; n < UBOUND ; n += 5 ) sum += n ; // all multiples of five
            for( long long n = 15 ; n < UBOUND ; n += 15 ) sum -= n ; // multiples of 15 have been added twice
        }
                                                          // so subtract multiples of 15
        std::cout << "sum == " << sum <<       "\n---------------------\n\n" ; ;
    }

    {
        std::cout << "one loop with clever (needlessly clever?) increment:\n" ;
        long long sum = 0 ;

        {
            cpu_timer timer ;

            // where n is a multiple of either three or five (or both)
            // the smaller of (3-n%3) and (5-n%5) gives the increment required
            // to get to the next higher multiple of three or five (or both)
            for( long long n = 3 ; n < UBOUND ; n += std::min( (3-n%3), (5-n%5) ) ) sum += n ;
        }

        std::cout << "sum == " << sum <<       "\n---------------------\n\n" ; ;
    }

    {
        std::cout << "constexpr: demand evaluation at compile time:\n" ;
        long long sum = 0 ;

        {
            cpu_timer timer ;
            // 3 + 6 + ... + 999999999 == 3 * ( 1 + 2 + 3 + ... + 333333333 ) == 3 * 333333333 * 333333334 / 2
            constexpr long long N = UBOUND - 1 ;
            constexpr long long sum3 = 3 * (N/3) * ( N/3 + 1 ) / 2 ; // sum of multiples of three
            constexpr long long sum5 = 5 * (N/5) * ( N/5 + 1 ) / 2 ; // sum of multiples of five
            constexpr long long sum15 = 15 * (N/15) * ( N/15 + 1 ) / 2 ; // sum of multiples of fifteen

            sum = sum3 + sum5 - sum15 ;
        }

        std::cout << "sum == " << sum <<       "\n---------------------\n\n" ; ;
    }
}

echo && echo '===== clang++/libc++ =======' && echo && clang++ -std=c++1z -stdlib=libc++ -Wall -Wextra -pedantic-errors -O3 main.cpp -lsupc++ && ./a.out
echo && echo && echo '===== g++/libstdc++ =======' && echo && g++ -std=c++1z -Wall -Wextra -pedantic-errors -O3 main.cpp && ./a.out

===== clang++/libc++ =======

one loop with an if (logical or in condition):
1460 millisecs (processor)
sum == 37333333266666668
---------------------

one loop with if - else if construct:
1340 millisecs (processor)
sum == 37333333266666668
---------------------

three loops: simple, transparent code; no conditionals in the loops)
(the optimiser can figure out everything about what is going on):
0 millisecs (processor)
sum == 37333333266666668
---------------------

one loop with clever (needlessly clever?) increment:
1380 millisecs (processor)
sum == 37333333266666668
---------------------

constexpr: demand evaluation at compile time:
0 millisecs (processor)
sum == 37333333266666668
---------------------



===== g++/libstdc++ =======

one loop with an if (logical or in condition):
1220 millisecs (processor)
sum == 37333333266666668
---------------------

one loop with if - else if construct:
1050 millisecs (processor)
sum == 37333333266666668
---------------------

three loops: simple, transparent code; no conditionals in the loops)
(the optimiser can figure out everything about what is going on):
0 millisecs (processor)
sum == 37333333266666668
---------------------

one loop with clever (needlessly clever?) increment:
1270 millisecs (processor)
sum == 37333333266666668
---------------------

constexpr: demand evaluation at compile time:
0 millisecs (processor)
sum == 37333333266666668
---------------------

http://coliru.stacked-crooked.com/a/46aba2358d793e59
SakurasouBusters (732)
@JLBorges
Why did you not use the standard header <chrono> to efficiently measure the time?
JLBorges (13770)
The clocks in <chrono> measure the wrong time for this purpose.

For more information, start reading this thread here onwards http://www.cplusplus.com/forum/beginner/146620/#msg771119
There is a code example in the last post in that thread.

To quote Esslercuffi from that thread:
the chrono clocks measure actual time elapsed regardless of which programs are recieving processing time, not time spend by this program on processing.
lastchance (6980)
I don't think @Skoliro realised what he/she had sparked off!

I'll stick with the sum and difference of arithmetic series though - it gives an explicit formula and the number of arithmetic operations is independent of the upper bound (at least as long as m and n are co-prime: finding and taking out the HCF probably makes it more expensive).

Many thanks for your efforts, though, @JLBorges.

For the record here are some more Project Euler questions:
https://projecteuler.net/archives
Topic archived. No new replies allowed.