Project Euler 216 - Investigating the primality of numbers of the form 2n2-1

Official link:

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:

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