MAX = 10**6 + 2
primes = [True]*MAX
primes[0] = primes[1] = False
for i in range(MAX):
if primes[i]:
for j in range(i + i, MAX, i):
primes[j] = False
class Solution:
def minJumps(self, nums: List[int]) -> int:
queue = deque()
indexs = defaultdict(list)
for i, val in enumerate(nums):
indexs[val].append(i)
mx = max(nums)
queue.append((0, 0))
n = len(nums)
visited = [False]*n
visited[0] = True
primesSet = set()
while queue:
current, step = queue.popleft()
if current == n - 1:
return step
if current + 1 < n and not visited[current + 1]:
visited[current + 1] = True
queue.append((current + 1, step + 1))
if current - 1 >= 0 and not visited[current - 1]:
visited[current - 1] = True
queue.append((current - 1, step + 1))
if primes[nums[current]] and nums[current] not in primesSet:
c = nums[current]
mult = 1
while c*mult <= mx:
nx=c*mult
for nxt in indexs[c*mult]:
if not visited[nxt]:
visited[nxt] = True
queue.append((nxt, step + 1))
mult += 1
primesSet.add(nums[current])
return -1