How to optimize BFS for “Minimum Jumps to Reach End via Prime Teleportation” (LeetCode 3629)?

I’m working on the problem
3629. Minimum Jumps to Reach End via Prime Teleportation
And my current solution is getting TLE (Time Limit Exceeded).

My Current Approach

I’m using:

BFS for shortest path

Prime checking during traversal

For every prime value, I scan the entire array to find divisible numbers

Simplified Code

queue<int> q; vector<int> vis(n, 0); q.push(0); vis[0] = 1; while (!q.empty()) { int i = q.front(); q.pop(); // adjacent moves if (i + 1 < n && !vis[i + 1]) { vis[i + 1] = 1; q.push(i + 1); } if (i - 1 >= 0 && !vis[i - 1]) { vis[i - 1] = 1; q.push(i - 1); } // teleportation if (isPrime(nums[i])) { for (int j = 0; j < n; j++) { if (j != i && nums[j] % nums[i] == 0 && !vis[j]) { vis[j] = 1; q.push(j); } } } }

What I Want to Understand

How can this BFS be optimized?

Is there a preprocessing technique using:

sieve,

prime factors,

hashmap/grouping,
that avoids repeatedly scanning the array?

What is the optimal time complexity for this problem?

I’d appreciate explanations of the data structure or graph modeling approach rather than only the final code.