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)
class Solution {
    private boolean[] sieve;

    private void runSieve() {
        sieve = new boolean[100000];
        Arrays.fill(sieve, true);
        sieve[0] = false;
        sieve[1] = false;
        for (int i = 2; i < 100000; i++) {
            if (sieve[i]) {
                for (int j = 2 * i; j < 100000; j += i) {
                    sieve[j] = false;
                }
            }
        }
    }

    private int solve(int n, int m) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.add(new int[] {n, n});
        Set<Integer> visited = new HashSet<>();

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int sum = top[0], cur = top[1];

            if (visited.contains(cur)) {
                continue;
            }
            visited.add(cur);

            if (cur == m) {
                return sum;
            }

            char[] s = String.valueOf(cur).toCharArray();
            for (int i = 0; i < s.length; i++) {
                char c = s[i];

                if (s[i] < '9') {
                    s[i] = (char) (s[i] + 1);
                    int next = Integer.parseInt(new String(s));
                    if (!sieve[next] && !visited.contains(next)) {
                        pq.add(new int[] {sum + next, next});
                    }
                    s[i] = c;
                }

                if (s[i] > '0' && !(i == 0 && s[i] == '1')) {
                    s[i] = (char) (s[i] - 1);
                    int next = Integer.parseInt(new String(s));
                    if (!sieve[next] && !visited.contains(next)) {
                        pq.add(new int[] {sum + next, next});
                    }
                    s[i] = c;
                }
            }
        }

        return -1;
    }

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