Project Euler 146 - Investigating a Prime Pattern

Official link: https://projecteuler.net/problem=146

Thought Process

The first thing I noticed was that n must be even, if it was odd then n^2+1 would be even and not prime. Which is a good start reducing the cases by half.

But the time consuming part is checking whether all the numbers are prime or not, and I came up with a pretty neat and extremely fast trick using Fermat's Little Theorem, which I later ended up discovering was called Fermat Primality Testing.

This means if we try a bunch of different values for a and this holds true then p is probably prime. I use a = 2 first to filter the cases down and because we will be testing 6 different cases it is highly unlikely we get 6 consecutive fake primes in a row.

Using this alone, the code still takes around 2.5 minutes, however it can be again sped up by investigating n mod (3,5,7) but I will leave that to you.

Another thing to note is that checking if they are prime does not mean they are consecutive!

Interactive Code

Enter a number (yourinput)

Code will output the sum of all such n less than yourinput

Note: Code is not super fast, 10^7 takes about 2.5 seconds

Page updated

Google Sites

Report abuse