Project Euler 518 - Prime Triples and Geometric Sequences

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

Thought Process

We are looking for primes a < b < c such that a+1, b+1, c+1 form a geometric sequence. If we do a triple loop of all the primes the code will take forever so we must think of a smarter way to generate the geometric sequence.

All we need to do is loop through z, then x, then y (this is faster) and check if zzx - 1, zxy - 1, and xyy - 1 are all prime.

The fastest way to do this is to create the Sieve of Eratosthenes (See Essential Functions), because if we can a list of primes it would take O(n) time (where n is the size of the list) to check if a prime is in the list, but checking if list[prime] = True is O(1)

Interactive Code

Enter an integer < 10^7 (yourinput), for speed reasons, anything above 10^7 takes about 5 seconds

Code will output S(yourinput)

Page updated

Google Sites

Report abuse