Since I'm currently looking for a job I've started going through the
exercises from Project Euler. The idea
is to get some practice in the sort of programming problems that are given in
interviews, refresh my C++ knowledge which has gotten rather rusty, and provide
some code samples for potential employers.
Problem 1: Summing Multiples of 3 or 5
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.
This is a rather trivial problem, so I'll skip any discussion of it and just
present my solution.
#include <iostream>
int main()
{
int sum = 0;
for (int i=3; i<1000; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i;
}
}
std::cout << sum << std::endl;
return 0;
}
Problem 2: Summing Even Fibonacci Numbers
Each new term in the Fibonacci sequence is generated by adding the previous two
terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed
four million, find the sum of the even-valued terms.
Like the previous one, this is too trivial for any discussion.
#include <iostream>
int main()
{
long sum = 0;
long a = 1, b = 2;
while (b < 4000000) {
if (b % 2 == 0) {
sum += b;
}
long temp = b + a;
a = b;
b = temp;
}
std::cout << sum << std::endl;
return 0;
}
Problem 3: Largest Prime Factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
There are two moderately interesting things about this problem. The first is
that it involves primality testing, which is slightly tricky. Naive solutions
are quite easy, but more efficient solutions are much more tricky. I've stuck to
the naive approach, since the numbers aren't sufficiently large to justify
writing a complicated algorithm.
The second moderately interesting point is that this problem uses numbers
outside the guaranteed range of a C++ long integer. Because of this, I used the
long long type, which isn't standard in C++ yet (though it is widely
supported).
#include <iostream>
// long long is not strict C++, unfortunately.
bool is_prime(long long val)
{
if (val < 2) return false;
if (val == 2) return true;
if (val % 2 == 0) return false;
long long i = 3;
while (i * i <= val) {
if (val % i == 0) {
return false;
}
i += 2;
}
return true;
}
int main() {
long long val = 600851475143LL;
long long i = 2;
long long largest = 0;
while (i * i <= val) {
if (is_prime(i) && val % i == 0) {
largest = i;
}
i++;
}
std::cout << largest << std::endl;
return 0;
}
Problem 4: Largest Palindromic Number
A palindromic number reads the same both ways. The largest palindrome made from
the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
This was the first problem that I got wrong initially. The mistake I made was
to iterate over the numbers from largest to smallest, and take the first
palindrome product I found. This isn't actually the largest, however. It is
simply the result that happens to have the largest value for one of the two
factors. That is, the result I ended up with was 995 * 583 = 580085,
while the actual answer is 993 * 913 = 906609. I think this is a
somewhat understandable mistake, but certainly a type of error to watch out for.
#include <iostream>
#include <sstream>
bool is_palindrome(long val)
{
std::ostringstream sout;
sout << val;
std::string text(sout.str());
std::string reversed(text.rbegin(), text.rend());
return text == reversed;
}
int main()
{
long max = 0;
for (int i=99; i<1000; i++) {
for (int j=i; j<1000; j++) {
int val = i*j;
if (is_palindrome(val) && val > max) {
max = val;
}
}
}
std::cout << max << std::endl;
return 0;
}
Problem 5: Smallest Evenly Divisible Number
2520 is the smallest number that can be divided by each of the numbers from 1 to
10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the
numbers from 1 to 20?
There's not much to say about this one. The simple optimization of adding 20
on each iteration didn't occur to me immediately, like it probably should have.
#include <iostream>
bool is_divisible(long val)
{
for (int i=2; i<=20; i++) {
if (val % i != 0) return false;
}
return true;
}
int main()
{
for (long i=20; ; i+=20) {
if (is_divisible(i)) {
std::cout << i << std::endl;
break;
}
}
return 0;
}
