Project Euler 216 - Investigating the primality of numbers of the form 2n2-1
Official link: https://projecteuler.net/problem=216
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 2n2-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
Initialise an array, f, of length limit + 1 where f[x] = 2x^2 - 1
run through x = 2 to limit + 1
Let div = f[x], this will be our constant increment
if div > 1, we continue with the sieve
As article says we must divide f[x + k*div] by div as many times as possible.
let curr1 go from x + div -> limit, with a div jump each time
divide f[curr1] by div till you can't anymore
As article says we must divide f[-x + k*div] by div as many times as possible.
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.
Enter a number (yourinput)
Code will output the amount of numbers t(n) which are prime such that n < yourinput