Project Euler 425 - Prime Connection

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

Thought Process

This was one of my favourite Project Euler problems! It was a really fun coding challenge for me as I could theorize a solution very quickly but it took a lot of optimizations' before I could get an answer in an acceptable time.

My idea was to create a graph where each node is a prime and there is an edge between 2 primes if they are connected, and the weight of this edge is the larger prime. They we find the path from 2 to every prime such that the maximal element of the path is minimized. If the maximal element of this path is greater than the prime itself then it is not a 2 relative.

Then the problem clearly becomes implementing 2 parts:

1. Generate the graph efficiently

2. Make an algorithm to find this minimax (I call it minimax because we aim to minimize the maximal element of the path) path

I implemented my graph as an Adjacency List with weights using dictionaries. For example the graph[2] = {2: [(3, 3), (5, 5), (7, 7)]} since 2 is connected to 3, 5, 7 and the weight of this edge is 3, 5, 7 respectively

At first I tried just directly comparing every prime with every prime but it takes way too long and far too many unnecessary comparisons are made. 

Instead, for each prime, p, I directly find all the possible changes, n, larger than the original prime that can be made (change every digit, and add every digit Infront), and if this change is prime I add the edge (n, n) to graph[p] and I add (p, n) to graph[n]. 

Below is my implementation of step 1.

Interactive Code

Input an integer (yourinput)

Code will output F(yourinput)