I've been working through the British Informatic Olympiad's 2016 Paper, and I've been struggling with some of the larger cases for question 3, specifically the larger cases on the mark scheme (the 3 before last specifically).
- Two prime numbers are connected if the difference between them is 2n for some whole number n ≥ 0.
- A path is a sequence of (at least two) prime numbers, without repetition, where adjacent numbers in the sequence are connected. If the first number in the sequence is p and the last number is q then we say the path is between p and q.
- The length of a path is the total number of prime numbers used. There may be multiple paths between two prime numbers; the lengths of these paths may be different.
Write a program to determine the length of the shortest path between two primes. Your program should accept three integers in order: l (4 ≤ l ≤ 224) indicating the highest value you are allowed to use, followed by the primes p then q (2 ≤ p < q < l). You will only be given input where there is a path between p and q using values below l. You should output the length of the shortest path.
Inputs I was struggling with:
614700 3643 90149 | outputs 18 987654 3643 90149 | outputs 16 1000000 2 968137 | outputs 18
How can I improve its performance?
import math primes = None upper_limit = 0 powers_of_two =  class Node: def __init__(self, value, parent): self.value = value self.parent = parent def get_adjacent(self): for i in powers_of_two: if (self.value + i < upper_limit and self.parent != self.value + i and self.value + i in primes): yield Node(i+self.value, self) if (self.value - i >= 2 and self.parent != self.value - i and self.value - i in primes): yield Node(self.value - i, self) def sieve(n): numbers = list(range(0, n)) for prime in numbers: if prime < 2: continue elif prime > n ** 0.5: break for i in range(prime ** 2, n, prime): numbers[i] = 0 return [x for x in numbers if x > 1] def bfs(f, to): f = Node(f, None) q = [f] visited = [f.value] while len(q) != 0: if q.value == to: return q else: for x in q.get_adjacent(): #print(q.value, x.value) if x.value not in visited: #print("added", x.value) visited.append(x.value) q.append(x) del q while True: inp = [int(x) for x in input().split(' ')] upper_limit = inp m = int(math.ceil(math.log2(inp))) if math.log2(inp) % 1 != 0 else int(math.log2(inp)) for i in range(0, m): powers_of_two.append(2**i) primes = sieve(inp) x = bfs(inp, inp) counter = 0 while x is not None: print(x.value) x = x.parent counter += 1 print("--------------------") print(counter)