Euler 9 in C
So I recently wrote an ugly solution to Project Euler’s problem #9. It was written in Python and even though every other Project Euler solution I wrote ran in less than one second, this one took over 18 seconds to get to the answer. Obviously it’s my fault for using a purely brute force algorithm.
Anyway, boredom is a great motivator and I just rewrote the exact same algorithm in C, just to see how much faster it would be.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <stdio.h> int is_triplet(int a, int b, int c) { return (((a < b) && (b < c)) && ((a * a + b * b) == (c * c))); } int main(void) { for (int a = 0; a < 1000; a++) for (int b = a + 1; b < 1000; b++) for (int c = b + 1; c < 1000; c++) if ((a + b + c == 1000) && is_triplet(a, b, c)) { printf("%d %d %d = %d\n", a, b, c, a * b * c); return 0; } } |
It’s the exact same algorithm, but instead of 18 seconds, it ran in 0.072s.
Update: And here’s the version suggested by Gustavo Niemeyer:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <stdio.h> int is_triplet(int a, int b, int c) { return ((a * a + b * b) == (c * c)); } int main(void) { for (int a = 1; a < 1000; a++) for (int b = a + 1; b < (1000 - a) / 2; b++) { int c = 1000 - a - b; if (is_triplet(a, b, c)) { printf("%d %d %d = %d\n", a, b, c, a * b * c); return 0; } } } |
It now runs in 0.002s 