Project Euler, Problems 6 through 10
While I'm in the process of looking for a job, I've been working through some practice problems for Project Euler and posting my solutions.
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, except that it took me a little while to be convinced of the correctness of the optimization of adding 20 on each loop. Of course i mod 20 = 0 implies that 20 * n = i for some integer n.
#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;
}
Problem 6: Sum of Squares, Square of Sum
The sum of the squares of the first ten natural numbers is, 12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Another generally boring problem, but this one did offer one mildly interesting optimization. Calculating the sum of sequential natural numbers can be done with a formula rather than looping through them with an accumulator. There may be a formula for the sum of squares also, but I don't know if there is off the top of my head, so I did that portion with a loop.
#include <iostream>
long square_of_sum(long max)
{
long sum = (max + 1) * max / 2;
return sum * sum;
}
long sum_of_squares(long max)
{
long sum = 0;
for (long i=1; i<=max; i++) {
sum += i * i;
}
return sum;
}
int main()
{
std::cout << square_of_sum(100) - sum_of_squares(100) << std::endl;
return 0;
}
Problem 7: 10001st Prime Number
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
Re-using is_prime() from an earlier problem (and not for the last time), this is trivial. I constrain the loop to only odd numbers as a simple optimization.
#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()
{
int count = 1;
long long test;
for (test=3; ; test+=2) {
if (is_prime(test)) {
if (++count == 10001) {
break;
}
}
}
std::cout << test << std::endl;
return 0;
}
Problem 8: Maximum Product of Consecutive Digits
Find the greatest product of five consecutive digits in the 1000-digit number.
I got this wrong the first time because I was thinking sum instead of product (which is perhaps a more interesting problem). Kind of ugly use of a global variable, but it gets the job done.
#include <iostream>
char digits[] =
"73167176531330624919225119674426574742355349194934"
"96983520312774506326239578318016984801869478851843"
"85861560789112949495459501737958331952853208805511"
"12540698747158523863050715693290963295227443043557"
"66896648950445244523161731856403098711121722383113"
"62229893423380308135336276614282806444486645238749"
"30358907296290491560440772390713810515859307960866"
"70172427121883998797908792274921901699720888093776"
"65727333001053367881220235421809751254540594752243"
"52584907711670556013604839586446706324415722155397"
"53697817977846174064955149290862569321978468622482"
"83972241375657056057490261407972968652414535100474"
"82166370484403199890008895243450658541227588666881"
"16427171479924442928230863465674813919123162824586"
"17866458359124566529476545682848912883142607690042"
"24219022671055626321111109370544217506941658960408"
"07198403850962455444362981230987879927244284909188"
"84580156166097919133875499200524063689912560717606"
"05886116467109405077541002256983155200055935729725"
"71636269561882670428252483600823257530420752963450";
long digit(int i)
{
return digits[i] - '0';
}
int main()
{
long largest = 0;
for (int i=0; digits[i+4]; i++) {
long product = digit(i) * digit(i+1) * digit(i+2) * digit(i+3) * digit(i+4);
if (product > largest) {
largest = product;
}
}
std::cout << largest << std::endl;
return 0;
}
Problem 9: Pythagorean Triplet
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
This one is slightly tricky if you want to avoid a lot of unnecessary tests, but overall there's not much to it.
#include <iostream>
int main()
{
int a, b, c;
for (a = 1; a < 998; a++) {
for (b = a+1; ; b++) {
c = 1000 - a - b;
if (c < b || c < a) break;
if (a*a + b*b == c*c) {
std::cout << a << ' ' << b << ' ' << c << std::endl;
std::cout << (a*b*c) << std::endl;
return 0;
}
}
}
return 0;
}
Problem 10: Sum of Primes
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
Using is_prime() again, there's not much to this other than the need to use long long again for the large sum.
#include <iostream>
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 sum = 2;
long tally = 1;
for (long i=3; i < 2000000; i+=2) {
if (is_prime(i)) {
sum += i;
tally++;
}
}
std::cout << sum << std::endl;
std::cout << tally << " primes found" << std::endl;
return 0;
}
