Thought Process

There are many ways to go about this problem, with modular tricks or finding numbers near the root and such but I did a similar problem before (problem 659) and I thought a sieve might work well. Luckily the exact same website that helped me implement a sieve for problem 659 made an article to sieve 2n²-1, see here: http://devalco.de/quadr_Sieb_2x%5E2-1.php

I implemented the sieve and got the answer in ~100 seconds

I briefly explain the sieve here

1. Initialise an array, f, of length limit + 1 where f[x] = 2x^2 - 1

2. run through x = 2 to limit + 1

   1. Let div = f[x], this will be our constant increment

   2. if div > 1, we continue with the sieve

      1. As article says we must divide f[x + k*div] by div as many times as possible.

         1. let curr1 go from x + div -> limit, with a div jump each time

         2. divide f[curr1] by div till you can't anymore

      2. As article says we must divide f[-x + k*div] by div as many times as possible.

         1. Same as above except with -x

If an f[x] is divisible by a number then it is not a prime, so I just keep track of which numbers have been divided.