/* 演算法 / Algorithm:
 * 1. 線性最小質因數篩 (SPF) 預先算好 spf[x]，使每個值能在 O(log x) 內分解。
 *    Build a smallest-prime-factor sieve so any value factors in O(log x).
 * 2. 對每個 nums[i] 取出相異質因數 p，把 i 放進 bucket[p]。
 *    For each value, push its index into bucket[p] for every distinct prime p.
 * 3. 從索引 0 做 BFS：鄰居是 i±1；若 nums[i] 是質數 p，再加上 bucket[p]
 *    內所有索引，然後清空該桶（同一個桶只展開一次，避免 O(n^2)）。
 *    BFS from index 0 with adjacency edges and prime-bucket edges; each
 *    bucket fires only once (we clear it after use) so total work is O(n).
 */
int minJumps(int* nums, int numsSize) {
    int n = numsSize;                                       // n 是陣列長度 / array length
    if (n == 1) return 0;                                   // 起點即終點 / already at goal

    int maxv = 1;                                           // 紀錄最大值 / track max value
    for (int i = 0; i < n; i++) {
        if (nums[i] > maxv) maxv = nums[i];                 // 比較並更新 / update if larger
    }

    /* ---- 最小質因數篩 / Smallest-prime-factor sieve ----
       calloc 配置記憶體並全填 0 / calloc allocates and zeroes the buffer */
    int* spf = (int*)calloc(maxv + 1, sizeof(int));
    for (int i = 2; i <= maxv; i++) {                       // 從 2 起檢查 / scan from 2
        if (spf[i] == 0) {                                  // 0 表示 i 是質數 / i is prime
            for (int j = i; j <= maxv; j += i) {            // 標記 i 的所有倍數 / mark multiples of i
                if (spf[j] == 0) spf[j] = i;                // 只在尚未填寫時寫入，保留最小者 / keep the smallest prime
            }
        }
    }

    /* ---- 第一輪：算每個質數桶要多少格 ----
       First pass: count how many entries each bucket will hold. */
    int* bcount = (int*)calloc(maxv + 1, sizeof(int));      // 桶大小 / bucket sizes
    for (int i = 0; i < n; i++) {
        int v = nums[i];                                    // v 是可破壞的拷貝 / mutable copy
        while (v > 1) {                                     // 拆掉所有質因數 / peel off all prime factors
            int p = spf[v];                                 // 取最小質因數 / smallest prime factor of v
            bcount[p]++;                                    // 此桶 +1 / bucket size += 1
            while (v % p == 0) v /= p;                      // 把 v 中所有 p 除掉，避免重複加 / strip all copies of p
        }
    }

    /* ---- 用前綴和算每個桶在扁平陣列中的起點 ----
       Prefix-sum the counts to get each bucket's start offset in a flat array. */
    int* boff = (int*)malloc((maxv + 2) * sizeof(int));     // boff[p] = 桶 p 起點 / start of bucket p
    boff[0] = 0;
    for (int i = 0; i <= maxv; i++) {
        boff[i + 1] = boff[i] + bcount[i];                  // 累加 / running sum
    }
    int total = boff[maxv + 1];                             // 所有桶總條目數 / total entries across all buckets

    int* bdata = (int*)malloc((total > 0 ? total : 1) * sizeof(int));  // 扁平資料區 / flat storage
    int* bfill = (int*)calloc(maxv + 1, sizeof(int));       // 各桶寫入指標 / per-bucket write cursor

    /* ---- 第二輪：把索引塞進桶 / Second pass: actually fill buckets. ---- */
    for (int i = 0; i < n; i++) {
        int v = nums[i];
        while (v > 1) {
            int p = spf[v];
            bdata[boff[p] + bfill[p]++] = i;                // 寫到桶尾並把指標往前推 / append and advance cursor
            while (v % p == 0) v /= p;
        }
    }

    /* ---- BFS 距離陣列與佇列 / BFS distance array and queue ---- */
    int* dist = (int*)malloc(n * sizeof(int));              // dist[i] = 從 0 到 i 的最短跳數 / shortest jumps to i
    for (int i = 0; i < n; i++) dist[i] = -1;               // -1 代表還沒拜訪 / unvisited sentinel

    int* queue = (int*)malloc(n * sizeof(int));             // 環狀不需要：節點最多入隊一次 / each node is pushed at most once
    int qh = 0, qt = 0;                                     // 頭尾指標 / head and tail cursors
    queue[qt++] = 0;                                        // 推入起點 / push start index
    dist[0] = 0;                                            // 起點距離為 0 / start has distance 0

    int ans = -1;                                           // 預設答案 / default answer
    while (qh < qt) {                                       // 佇列非空 / while queue is non-empty
        int i = queue[qh++];                                // 取出隊首 / pop the front
        if (i == n - 1) { ans = dist[i]; break; }           // 抵達終點即可離開 / early exit at goal
        int d = dist[i];                                    // 當前距離 / current distance

        /* 相鄰步 / Adjacent steps */
        if (i + 1 < n && dist[i + 1] == -1) {               // 右鄰未訪問 / right neighbor unvisited
            dist[i + 1] = d + 1;                            // 距離 +1 / one more jump
            queue[qt++] = i + 1;                            // 入隊 / enqueue
        }
        if (i - 1 >= 0 && dist[i - 1] == -1) {              // 左鄰未訪問 / left neighbor unvisited
            dist[i - 1] = d + 1;
            queue[qt++] = i - 1;
        }

        /* 質數傳送 / Prime teleportation (only when nums[i] itself is prime) */
        int v = nums[i];
        if (v >= 2 && spf[v] == v) {                        // spf[v]==v 即 v 是質數 / v is prime
            int sz = bcount[v];                             // 桶內剩多少個 / remaining bucket size
            int start = boff[v];                            // 桶起始位置 / bucket start offset
            for (int k = 0; k < sz; k++) {
                int j = bdata[start + k];                   // 桶內第 k 個索引 / k-th index in the bucket
                if (dist[j] == -1) {                        // 尚未拜訪才更新 / only first visit wins (BFS optimal)
                    dist[j] = d + 1;
                    queue[qt++] = j;
                }
            }
            bcount[v] = 0;                                  // 清空桶：之後同樣的 p 不再重展 / clear bucket so each prime fires once
        }
    }

    /* 釋放所有 malloc/calloc 配置的記憶體 / Free every heap allocation */
    free(spf); free(bcount); free(boff);
    free(bdata); free(bfill); free(dist); free(queue);
    return ans;
}