Project Euler source code

Euler.cpp

#include <iostream>
#include <cmath>
#include <cstdint>
#include <memory>
#include <vector>
#include <chrono>
#include <thread>
using namespace std;
using namespace std::chrono;
using namespace std::this_thread;
void test(uint64_t(*f)()) {
    auto a = high_resolution_clock::now();
    uint64_t r = f();
    auto b = high_resolution_clock::now();
    cout << "Time: " << duration_cast<duration<double, milli>>(b - a).count() << " ms" << endl;
    cout << "Result: " << r << endl;
}
vector<bool> make_sieve(uint64_t s) {
    vector<bool> sieve(s);
    uint64_t ss = static_cast<uint64_t>(sqrt(s) + 1);
    for (uint64_t i = 2; i < ss; ++i) {
        for (uint64_t j = i * i; j < s; j += i) {
            sieve[j] = true;
        }
    }
    return sieve;
}
uint64_t p1() {
    uint64_t n = 1000;
    --n;
    uint64_t n3 = n / 3;
    n3 = n3 * (n3 + 1) * 3 / 2;
    uint64_t n5 = n / 5;
    n5 = n5 * (n5 + 1) * 5 / 2;
    uint64_t n15 = n / 15;
    n15 = n15 * (n15 + 1) * 15 / 2;
    return n3 + n5 - n15;
}
uint64_t p2() {
    uint64_t s = 0;
    uint64_t n1 = 1;
    uint64_t n2 = 1;
    uint64_t n3 = 2;
    while (n3 <= 4000000) {
        s += n3;
        n1 = n2 + n3;
        n2 = n3 + n1;
        n3 = n1 + n2;
    }
    return s;
}
uint64_t p3() {
    uint64_t n = 600851475143;
    uint64_t s = static_cast<uint64_t>(sqrt(n) + 1);
    auto sieve(make_sieve(s));
    for (uint64_t i = 2; i < s; ++i) {
        if (!sieve[i]) for (;;) {
            uint64_t d = n / i;
            uint64_t r = n % i;
            if (r != 0) break;
            n = d;
            s = static_cast<uint64_t>(sqrt(n) + 1);
        }
    }
    return n;
}
uint64_t p4() {
    char buf[0x10];
    uint32_t best = 0;
    for (uint32_t i = 999; i >= 100; --i) {
        for (uint32_t j = 999; j >= i; --j) {
            uint32_t p = i * j;
            if (p <= best) continue;
            int n = sprintf_s(buf, "%u", p);
            bool found = true;
            for (int m = 0; m < n >> 1; ++m) {
                if (buf[n - m - 1] != buf[m]) {
                    found = false;
                    break;
                }
            }
            if (found) best = p;
        }
    }
    return best;
}
uint64_t p5() {
    uint32_t s = 20;
    auto sieve(make_sieve(s));
    uint8_t buf[21] = {};
    for (uint8_t i = 2; i <= s; ++i) {
        for (uint8_t n = i, j = 2; n != 1; ++j) {
            if (!sieve[j]) {
                uint8_t c = 0;
                for (;;) {
                    uint8_t d = n / j;
                    uint8_t r = n % j;
                    if (r != 0) break;
                    n = d;
                    ++c;
                }
                if (buf[j] < c) buf[j] = c;
            }
        }
    }
    uint32_t r = 1;
    for (uint8_t i = 1; i <= s; ++i) {
        for (uint8_t j = buf[i]; j; --j) {
            r *= i;
        }
    }
    return r;
}
uint64_t p6() {
    uint64_t s1 = 0, s2 = 0;
    for (uint64_t i = 1; i <= 100; ++i) {
        s1 += i * i;
        s2 += i;
    }
    uint64_t d = s2 * s2 - s1;
    return d;
}
uint64_t p7() {
    uint64_t s = 10001;
    auto sieve(make_sieve(104744));
    for (uint64_t i = 2, n = 0;; ++i) {
        if (!sieve[i]) {
            if (++n == s) {
                return i;
            }
        }
    }
}
uint64_t p8() {
    char s[] ="\
73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450";
    uint8_t n[1000];
    for (uint16_t i = 0; i < 1000; ++i) {
        n[i] = s[i] - '0';
    }
    uint32_t b = 0;
    for (uint16_t i = 0; i < 996; ++i) {
        uint32_t p = n[i + 0] * n[i + 1] * n[i + 2] * n[i + 3] * n[i + 4];
        if (p > b) b = p;
    }
    return b;
}
uint64_t p9() {
    for (uint32_t a = 1; a + (a + 1) + (a + 2) <= 1000; ++a) {
        for (uint32_t b = a + 1; a + b + (b + 1) <= 1000; ++b) {
            uint32_t c = 1000 - (a + b);
            if (a * a + b * b == c * c) {
                return a * b * c;
            }
        }
    }
    return 0;
}
uint64_t p10() {
    auto sieve(make_sieve(2000000));
    uint64_t s = 0;
    for (uint64_t i = 2; i < 2000000; ++i) {
        if (!sieve[i]) {
            s += i;
        }
    }
    return s;
}
uint64_t p11() {
    uint8_t a[20][20] = {
         8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8,
        49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0,
        81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65,
        52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91,
        22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80,
        24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50,
        32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70,
        67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21,
        24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
        21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95,
        78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92,
        16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57,
        86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
        19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40,
         4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
        88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
         4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36,
        20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16,
        20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54,
         1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48};
    uint32_t max = 0;
    for (uint8_t x = 0; x <= 16; ++x) {
        for (uint8_t y = 0; y <= 16; ++y) {
            uint32_t n = a[x][y] * a[x + 1][y + 1] * a[x + 2][y + 2] * a[x + 3][y + 3];
            if (n > max) max = n;
            uint32_t m = a[x + 3][y] * a[x + 2][y + 1] * a[x + 1][y + 2] * a[x][y + 3];
            if (m > max) max = m;
        }
    }
    for (uint8_t x = 0; x < 20; ++x) {
        for (uint8_t y = 0; y <= 16; ++y) {
            uint32_t n = a[x][y] * a[x][y + 1] * a[x][y + 2] * a[x][y + 3];
            if (n > max) max = n;
        }
    }
    for (uint8_t x = 0; x <= 16; ++x) {
        for (uint8_t y = 0; y < 20; ++y) {
            uint32_t n = a[x][y] * a[x + 1][y] * a[x + 2][y] * a[x + 3][y];
            if (n > max) max = n;
        }
    }
    return max;
}
int main() {
    test(p11);
}