058_spiral_primes.cpp

/*
 * Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.
 *
 * 37 36 35 34 33 32 31
 * 38 17 16 15 14 13 30
 * 39 18  5  4  3 12 29
 * 40 19  6  1  2 11 28
 * 41 20  7  8  9 10 27
 * 42 21 22 23 24 25 26
 * 43 44 45 46 47 48 49
 *
 * It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting
 * is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
 *
 * If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed.
 * If this process is continued, what is the side length of the square spiral for which the ratio of primes along
 * both diagonals first falls below 10%?
 */

#include <iostream>
#include <vector>
#include "MyLib_cpp.h"

using namespace std;

int main() {

    // enough for < 4759123141
    vector<num> witnesses = {2, 7, 61};

    unsigned int  primes = 3;
    unsigned long index  = 9;

    double primeRatio = 1;

    for (int sideLength = 5; index < 4759123141; sideLength += 2) {
        for (int corner = 0; corner < 4; ++corner) {
            index += sideLength - 1;
            if (millerRabin(index, witnesses)) {
                ++primes;
            }
        }
        primeRatio      = primes / (double) (sideLength * 2 - 1);
        if (primeRatio < 0.1) {
            cout << "Primes " << primes << endl;
            cout << "length " << sideLength << endl;
            cout << "Ratio  " << primeRatio << endl << endl;
            return 0;
        }
    }
    return -1;
}