/* 演算法 / Algorithm:
 * 1. 用 SPF 篩預算最小質因數 / SPF sieve up to max(nums).
 * 2. 為每個出現的相異質因數 p 建桶 bucket[p] / build bucket[p] of indices divisible by p.
 * 3. BFS：相鄰邊 + 若 nums[i] 是質數 p 則展開 bucket[p] 後清空 / BFS with prime-bucket edges, clearing buckets after use.
 */
class Solution {
public:
    int minJumps(vector<int>& nums) {
        int n = (int)nums.size();                                 // 陣列長度 / array length
        if (n == 1) return 0;                                     // 已在終點 / already at goal

        // *max_element 回傳指向最大元素的迭代器，前面加 * 取值 / returns iterator; * dereferences it
        int maxv = *max_element(nums.begin(), nums.end());

        // vector<int>(size, init): 建立大小為 size、初值為 init 的動態陣列 / sized + initialized vector
        vector<int> spf(maxv + 1, 0);
        for (int i = 2; i <= maxv; ++i) {
            if (spf[i] == 0) {                                    // i 是質數 / i is prime
                for (int j = i; j <= maxv; j += i) {              // 走訪所有倍數 / walk multiples
                    if (spf[j] == 0) spf[j] = i;                  // 只在還沒寫過時寫，保留最小 / keep smallest factor
                }
            }
        }

        // unordered_map: 雜湊表，平均 O(1) 查找 / hash map with avg O(1) lookup
        // vector<int>: 每個質數對應的索引列表 / per-prime list of indices
        unordered_map<int, vector<int>> bucket;
        for (int i = 0; i < n; ++i) {
            int v = nums[i];
            while (v > 1) {                                       // 持續拆出質因數 / peel prime factors
                int p = spf[v];
                bucket[p].push_back(i);                           // 加進桶尾 / append index to bucket
                while (v % p == 0) v /= p;                        // 把所有 p 除掉，避免同一個 p 加兩次 / strip all copies of p
            }
        }

        vector<int> dist(n, -1);                                  // -1 表示未訪 / -1 = unvisited
        queue<int> q;                                             // STL FIFO 佇列 / FIFO queue
        q.push(0);
        dist[0] = 0;

        while (!q.empty()) {
            int i = q.front();                                    // 看隊首 / peek front
            q.pop();                                              // 真正彈出 / pop it (q.pop returns void)
            if (i == n - 1) return dist[i];                       // 到終點即返回 / early exit
            int d = dist[i];

            // 範圍 for + initializer_list 一次處理兩個鄰居 / range-for over a brace-list iterates {i-1, i+1}
            for (int ni : {i - 1, i + 1}) {
                if (ni >= 0 && ni < n && dist[ni] == -1) {        // 邊界內且未訪 / in-bounds and unvisited
                    dist[ni] = d + 1;
                    q.push(ni);
                }
            }

            int v = nums[i];
            if (v >= 2 && spf[v] == v) {                          // v 是質數 / v is prime
                auto it = bucket.find(v);                         // it 是迭代器 / iterator into the map
                if (it != bucket.end()) {                         // 桶存在 / bucket exists
                    for (int j : it->second) {                    // it->second 是 vector<int> / second = the index list
                        if (dist[j] == -1) {
                            dist[j] = d + 1;
                            q.push(j);
                        }
                    }
                    it->second.clear();                           // 清空桶以避免重展 / clear so each prime fires once
                }
            }
        }
        return dist[n - 1];                                       // 理論上必能到達 / always reachable in practice
    }
};