1class Solution {
2    // Upper bound for the precomputed prime factor table.
3    private static final int MX = 1000001;
4
5    // factors[v] holds the list of distinct prime factors of v.
6    private static final List<Integer>[] FACTORS = new List[MX];
7
8    // Static block: precompute the prime factors for every value in [0, MX)
9    // using a sieve. This runs once when the class is loaded.
10    static {
11        // Initialize an empty list for every value.
12        for (int i = 0; i < MX; i++) {
13            FACTORS[i] = new ArrayList<>();
14        }
15        // Sieve of Eratosthenes style: if FACTORS[i] is empty, then i is prime.
16        for (int i = 2; i < MX; i++) {
17            if (FACTORS[i].isEmpty()) {
18                // Add prime i as a factor to all of its multiples.
19                for (int j = i; j < MX; j += i) {
20                    FACTORS[j].add(i);
21                }
22            }
23        }
24    }
25
26    public int minJumps(int[] nums) {
27        int n = nums.length;
28
29        // graph: maps a prime factor -> list of indices whose value contains that prime.
30        // Indices sharing a common prime factor can be reached from one another.
31        Map<Integer, List<Integer>> graph = new HashMap<>();
32        for (int i = 0; i < n; i++) {
33            int value = nums[i];
34            for (int prime : FACTORS[value]) {
35                graph.computeIfAbsent(prime, k -> new ArrayList<>()).add(i);
36            }
37        }
38
39        // BFS to find the minimum number of jumps from index 0 to index n - 1.
40        int answer = 0;
41        boolean[] visited = new boolean[n];
42        visited[0] = true;
43
44        Deque<Integer> queue = new ArrayDeque<>();
45        queue.offer(0);
46
47        while (true) {
48            // nextQueue holds the indices discovered at the next BFS level.
49            Deque<Integer> nextQueue = new ArrayDeque<>();
50
51            for (int i : queue) {
52                // Reached the last index: current level count is the answer.
53                if (i == n - 1) {
54                    return answer;
55                }
56
57                // Retrieve the group of indices sharing nums[i]'s prime factor.
58                // Note: this references the actual list stored in the map, so the
59                // adjacent indices appended below and the later clear() reuse it.
60                List<Integer> neighbors = graph.getOrDefault(nums[i], new ArrayList<>());
61
62                // Add the natural adjacent indices: i + 1 and i - 1.
63                neighbors.add(i + 1);
64                if (i > 0) {
65                    neighbors.add(i - 1);
66                }
67
68                // Visit all reachable neighbors.
69                for (int j : neighbors) {
70                    if (!visited[j]) {
71                        visited[j] = true;
72                        nextQueue.offer(j);
73                    }
74                }
75
76                // Clear the group so this prime-factor cluster is not processed
77                // again from any other index (an optimization that avoids
78                // redundant edge expansions).
79                neighbors.clear();
80            }
81
82            // Advance to the next BFS level.
83            queue = nextQueue;
84            answer++;
85        }
86    }
87}
88

1// Upper bound for precomputing prime factors.
2const int kMaxValue = 1e6 + 1;
3
4// factors[i] stores all distinct prime factors of i.
5vector<int> factors[kMaxValue];
6
7// Precompute distinct prime factors for every number using a sieve.
8// This runs once before any Solution is instantiated.
9int init = [] {
10    for (int i = 2; i < kMaxValue; ++i) {
11        // If factors[i] is empty, then i has not been marked => i is prime.
12        if (factors[i].empty()) {
13            // Mark i as a prime factor for all of its multiples.
14            for (int j = i; j < kMaxValue; j += i) {
15                factors[j].push_back(i);
16            }
17        }
18    }
19    return 0;
20}();
21
22class Solution {
23public:
24    int minJumps(vector<int>& nums) {
25        int n = nums.size();
26
27        // Map from a prime factor to all indices whose value contains that factor.
28        unordered_map<int, vector<int>> primeToIndices;
29        for (int i = 0; i < n; ++i) {
30            int value = nums[i];
31            for (int prime : factors[value]) {
32                primeToIndices[prime].push_back(i);
33            }
34        }
35
36        int steps = 0;
37
38        // Standard BFS over indices to find the shortest path to the last index.
39        vector<bool> visited(n, false);
40        visited[0] = true;
41
42        queue<int> currentLevel;
43        currentLevel.push(0);
44
45        while (true) {
46            queue<int> nextLevel;
47
48            // Process every index reachable in the current number of steps.
49            while (!currentLevel.empty()) {
50                int i = currentLevel.front();
51                currentLevel.pop();
52
53                // Reached the last index; current step count is the answer.
54                if (i == n - 1) {
55                    return steps;
56                }
57
58                // Collect all candidate neighbors:
59                // 1) Indices sharing the same value-based group (teleport jumps).
60                vector<int> neighbors = primeToIndices[nums[i]];
61                // 2) The adjacent index to the right.
62                neighbors.push_back(i + 1);
63                // 3) The adjacent index to the left (if it exists).
64                if (i > 0) {
65                    neighbors.push_back(i - 1);
66                }
67
68                // Enqueue all unvisited neighbors for the next BFS level.
69                for (int next : neighbors) {
70                    if (!visited[next]) {
71                        visited[next] = true;
72                        nextLevel.push(next);
73                    }
74                }
75
76                // Clear this group so its indices are never reprocessed,
77                // which keeps the overall BFS linear in total edges.
78                primeToIndices[nums[i]].clear();
79            }
80
81            // Advance BFS to the next level.
82            currentLevel = nextLevel;
83            ++steps;
84        }
85    }
86};
87```
88
89A note on the code's behavior: the neighbor lookup uses `primeToIndices[nums[i]]`, meaning it groups indices by the **value** `nums[i]` interpreted as a key into a map that was populated by **prime factors**. This works correctly when values themselves are prime (the key coincides with a prime factor entry). If you intended to jump between any indices sharing **any** common prime factor, you would loop over `factors[nums[i]]` and gather indices from each prime group:
90
91```cpp
92// Alternative: jump between indices sharing any common prime factor.
93for (int prime : factors[nums[i]]) {
94    for (int next : primeToIndices[prime]) {
95        if (!visited[next]) {
96            visited[next] = true;
97            nextLevel.push(next);
98        }
99    }
100    primeToIndices[prime].clear();
101}
102

1// Upper bound for precomputing prime factors (constraint limit + 1)
2const MAX = 1000001;
3
4// factors[i] stores the list of distinct prime factors of i
5const factors: number[][] = Array(MAX);
6
7// Initialize each entry as an empty array
8for (let i = 0; i < MAX; i++) {
9    factors[i] = [];
10}
11
12// Sieve-based approach: for each prime i, mark it as a factor of all its multiples
13for (let i = 2; i < MAX; i++) {
14    // If factors[i] is empty, i has no smaller prime factor, so i is prime
15    if (factors[i].length === 0) {
16        for (let j = i; j < MAX; j += i) {
17            factors[j].push(i);
18        }
19    }
20}
21
22function minJumps(nums: number[]): number {
23    const n = nums.length;
24
25    // Map each prime factor to the list of indices whose value shares that prime
26    const primeToIndices = new Map<number, number[]>();
27    for (let i = 0; i < n; i++) {
28        const value = nums[i];
29        for (const prime of factors[value]) {
30            if (!primeToIndices.has(prime)) {
31                primeToIndices.set(prime, []);
32            }
33            primeToIndices.get(prime)!.push(i);
34        }
35    }
36
37    // BFS to find the minimum number of jumps from index 0 to index n - 1
38    let steps = 0;
39    const visited: boolean[] = new Array(n).fill(false);
40    visited[0] = true;
41    let queue: number[] = [0];
42
43    while (true) {
44        const nextQueue: number[] = [];
45
46        for (const i of queue) {
47            // Reached the last index; return the current step count
48            if (i === n - 1) {
49                return steps;
50            }
51
52            // Collect candidate neighbors:
53            // 1) All indices sharing a prime factor with nums[i]
54            const neighbors: number[] = [...(primeToIndices.get(nums[i]) || [])];
55            // 2) The next adjacent index
56            neighbors.push(i + 1);
57            // 3) The previous adjacent index (if valid)
58            if (i > 0) {
59                neighbors.push(i - 1);
60            }
61
62            // Visit all unvisited neighbors
63            for (const j of neighbors) {
64                if (!visited[j]) {
65                    visited[j] = true;
66                    nextQueue.push(j);
67                }
68            }
69
70            // Clear this value's prime group to prevent reprocessing
71            // (all members are now reachable, so the group is exhausted)
72            if (primeToIndices.has(nums[i])) {
73                primeToIndices.get(nums[i])!.length = 0;
74            }
75        }
76
77        queue = nextQueue;
78        steps++;
79    }
80}
81