#include <iostream>
#include <cmath>
#include <chrono>
#include <iomanip>
#include <sstream>
#include <string>

#define endl '\n'

bool is_prime(unsigned n) {
    if(n == 2 || n == 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false;

    unsigned i=5, w=2;

    while(i*i <= sqrt(n)) {
        if(n%i == 0) return false;

        i += w;
        w = 6-w;
    }
    return true;
}

std::string ftos(float f, int precision = 5) {
    std::stringstream ss;
    ss << std::fixed << std::setprecision(precision) << f;
    return ss.str();
}

int main() {

    unsigned max = 10000000, counters_found = 0;
    bool flag = false;

    auto start = std::chrono::high_resolution_clock::now();

    // iterate thru odd numbers n
    for(unsigned i=3; i <= max; i += 2){

        for(unsigned j=1; j<i; j++) {
            if(is_prime(j*j + (i-j)*(i-j))) {
                flag = true;
                //std::cout << j << "^2 + " << (i-j) << "^2 is prime (" << i << ")" << endl;
                break;
            }
        }
        if(!flag) {
            std::cout << "counter: " << i << endl;
            ++counters_found;
        }
        flag = false;
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::duration<double>>(end-start);
    std::cout << counters_found
              << " counter(s) found for n <= "
              << max
              << ". \nSearch took "
              << ftos(duration.count(), 5)
              << " second(s) and approximately "
              << ftos(duration.count() / max, 10)
              << " second(s) per integer."
              << endl;

    return 0;
}