# Project Euler 216 - Investigating the primality of numbers of the form 2n2-1 # 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 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

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.

# Interactive Code

Enter a number (yourinput)

Code will output the amount of numbers t(n) which are prime such that n < yourinput