Solution.py

import heapq


class Solution:
    def __init__(self):
        self.sieve = []

    def run_sieve(self):
        self.sieve = [True] * 100000
        self.sieve[0], self.sieve[1] = False, False
        for i in range(2, 100000):
            if self.sieve[i]:
                for j in range(2 * i, 100000, i):
                    self.sieve[j] = False

    def solve(self, n, m):
        pq = []
        heapq.heappush(pq, (n, n))
        visited = set()

        while pq:
            sum_, cur = heapq.heappop(pq)

            if cur in visited:
                continue
            visited.add(cur)

            if cur == m:
                return sum_

            s = list(str(cur))
            for i in range(len(s)):
                c = s[i]

                if s[i] < '9':
                    s[i] = chr(ord(s[i]) + 1)
                    next_ = int(''.join(s))
                    if not self.sieve[next_] and next_ not in visited:
                        heapq.heappush(pq, (sum_ + next_, next_))
                    s[i] = c

                if s[i] > '0' and not (i == 0 and s[i] == '1'):
                    s[i] = chr(ord(s[i]) - 1)
                    next_ = int(''.join(s))
                    if not self.sieve[next_] and next_ not in visited:
                        heapq.heappush(pq, (sum_ + next_, next_))
                    s[i] = c

        return -1

    def minOperations(self, n, m):
        self.run_sieve()
        if self.sieve[n] or self.sieve[m]:
            return -1
        return self.solve(n, m)