project-euler/a233.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <chrono>
typedef long long int Int;

using namespace std;

vector<Int> primes;

void generatePrimes() {
    primes.push_back(2);
    primes.push_back(3);
    for (int i = 5; i < 1000000; i += 2) {
        bool isPrime = true;
        for (auto p : primes) {
            if ((int)p*(int)p > i)
                break;
            if (i % (int)p == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
            primes.push_back((Int)i);
    }
}

bool check420LatticePoints(Int n) {
    int latticePoints = 1;

    for (auto p : primes) {
        if (p*p > n)
            p = n;

        int multiplicity = 0;

        while (n % p == 0) {
            multiplicity++;
            n /= p;
        }

        if (multiplicity > 0 && p % 4 == 1) {
            latticePoints *= 2*multiplicity+1;

            if (latticePoints == 105)
                return true;

            if (105 % latticePoints != 0)
                return false;
        }

        if (n==1)
            return false;
    }
    return false;
}

int main() {
    Int max;
    cout << "N = ";
    cin >> max;

    auto start = chrono::system_clock::now();

    generatePrimes();

    auto middle = std::chrono::system_clock::now();

    std::chrono::duration<double> elapsed_seconds = middle-start;
    cout << "generating primes took: " << elapsed_seconds.count() << endl;

    Int count = 0, sum = 0;
    for (Int n = 10; n < max; n++) {
        if (check420LatticePoints(n)) {
            sum += n;
            count++;
        }
    }
    auto end = std::chrono::system_clock::now();

    elapsed_seconds = end-middle;
    cout << "finding 420s took: " << elapsed_seconds.count() << endl << endl;

    cout << "sum: " << sum << ", total: " << count;
    return 0;
}