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:
    vector<bool> sieve;
    void runSieve() {
        sieve.resize(100000, true);
        sieve[0] = false, sieve[1] = false;
        for (int i = 2; i < 1e5; ++i) {
            if (sieve[i]) {
                for (int j = 2 * i; j < 1e5; j += i) {
                    sieve[j] = false;
                }
            }
        }
    }
    int solve(int n, int m) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        unordered_set<int> vis;
        pq.push({n, n});
        while (!pq.empty()) {
            int sum = pq.top().first, cur = pq.top().second;
            pq.pop();
            if (vis.find(cur) != vis.end()) continue;
            vis.insert(cur);
            if (cur == m) return sum;
            string s = to_string(cur);
            for (int i = 0; i < s.size(); ++i) {
                char c = s[i];
                if (s[i] < '9') {
                    s[i]++;
                    int next = stoi(s);
                    if (!sieve[next] && vis.find(next) == vis.end()) {
                        pq.push({sum + next, next});
                    }
                    s[i] = c;
                }
                if (s[i] > '0' && !(i == 0 && s[i] == '1')) {
                    s[i]--;
                    int next = stoi(s);
                    if (!sieve[next] && vis.find(next) == vis.end()) {
                        pq.push({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);
    }
};
