Prime Run: a game about adding and subtracting prime numbers

(Disclaimer: Didn't read the article, just played the game straight away.)

Played until level 20 using a fairly basic heuristic ("click largest prime number that gets you closer, until you can find a clear solution path"). Without a limit or goal on number of steps to the target, it loses replay value relatively fast.

You can always reach divisibility by two in at most one step and divisibility by three in at most two steps * (etc.), so any target with small prime factors is trivially reached once you land in the vicinity by just repeatedly adding its smallest prime factor. If there's no small prime factors in your target, apply the above rule backwards from the target and you're in easy territory again. There's often shortcuts (e.g. you're 18 away from the target - you can replace 5x -2 with 2x -5 at some point along that route, and/or 3x -2 with 2x -3).

Finding optimal routes seems arduous by hand (even if I had memorized primes above 100, finding the remainders of your target and the possible steps remains intractable to me), but it might be an interesting programming exercise. I wonder if there is an even better solution than the obvious graph traversal one.

* Well, assuming you want to go a certain direction. Divisibility by three is technically also always just one step away.

Tangentially related, but my family (kids are 7-10) enjoys the "Prime Climb" [1] board game which deals with prime numbers.

[1] https://boardgamegeek.com/boardgame/159375/prime-climb

For any number up to 4x10^18, the solution is less than 4 steps. Use Goldbach's conjecture to split both numbers in a sum of two primes. Go from the source to 0, go from 0 to the target.

EDIT: Use goldbach's theorem on the difference between both numbers.