Omegacrash

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;
}