Digit Operations to Make Two Integers Equal
<p>You are given two integers <code>n</code> and <code>m</code> that consist of the <strong>same</strong> number of digits.</p>

<p>You can perform the following operations <strong>any</strong> number of times:</p>

<ul>
	<li>Choose <strong>any</strong> digit from <code>n</code> that is not 9 and <strong>increase</strong> it by 1.</li>
	<li>Choose <strong>any</strong> digit from <code>n</code> that is not 0 and <strong>decrease</strong> it by 1.</li>
</ul>

<p>The integer <code>n</code> must not be a <span data-keyword="prime-number">prime</span> number at any point, including its original value and after each operation.</p>

<p>The cost of a transformation is the sum of <strong>all</strong> values that <code>n</code> takes throughout the operations performed.</p>

<p>Return the <strong>minimum</strong> cost to transform <code>n</code> into <code>m</code>. If it is impossible, return -1.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 10, m = 12</span></p>

<p><strong>Output:</strong> <span class="example-io">85</span></p>

<p><strong>Explanation:</strong></p>

<p>We perform the following operations:</p>

<ul>
	<li>Increase the first digit, now <code>n = <u><strong>2</strong></u>0</code>.</li>
	<li>Increase the second digit, now <code>n = 2<strong><u>1</u></strong></code>.</li>
	<li>Increase the second digit, now <code>n = 2<strong><u>2</u></strong></code>.</li>
	<li>Decrease the first digit, now <code>n = <strong><u>1</u></strong>2</code>.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 4, m = 8</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>

<p><strong>Explanation:</strong></p>

<p>It is impossible to make <code>n</code> equal to <code>m</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 6, m = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>

<p><strong>Explanation:</strong>&nbsp;</p>

<p>Since 2 is already a prime, we can&#39;t make <code>n</code> equal to <code>m</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n, m &lt; 10<sup>4</sup></code></li>
	<li><code>n</code> and <code>m</code> consist of the same number of digits.</li>
</ul>
Graph; Math; Number Theory; Shortest Path; Heap (Priority Queue)
package main

import (
	"container/heap"
	"strconv"
)

type MinHeap [][]int

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.([]int))
}
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sieve []bool

func runSieve() {
	sieve = make([]bool, 100000)
	for i := range sieve {
		sieve[i] = true
	}
	sieve[0], sieve[1] = false, false
	for i := 2; i < 100000; i++ {
		if sieve[i] {
			for j := 2 * i; j < 100000; j += i {
				sieve[j] = false
			}
		}
	}
}

func solve(n int, m int) int {
	pq := &MinHeap{}
	heap.Init(pq)
	heap.Push(pq, []int{n, n})
	visited := make(map[int]bool)

	for pq.Len() > 0 {
		top := heap.Pop(pq).([]int)
		sum, cur := top[0], top[1]

		if visited[cur] {
			continue
		}
		visited[cur] = true

		if cur == m {
			return sum
		}

		s := []rune(strconv.Itoa(cur))
		for i := 0; i < len(s); i++ {
			c := s[i]

			if s[i] < '9' {
				s[i]++
				next, _ := strconv.Atoi(string(s))
				if !sieve[next] && !visited[next] {
					heap.Push(pq, []int{sum + next, next})
				}
				s[i] = c
			}

			if s[i] > '0' && !(i == 0 && s[i] == '1') {
				s[i]--
				next, _ := strconv.Atoi(string(s))
				if !sieve[next] && !visited[next] {
					heap.Push(pq, []int{sum + next, next})
				}
				s[i] = c
			}
		}
	}

	return -1
}

func minOperations(n int, m int) int {
	runSieve()
	if sieve[n] || sieve[m] {
		return -1
	}
	return solve(n, m)
}
