Hints required for logic formation

#1

could you please give me some hints regarding this question for the logic formation of the code or some video for a better understanding of the required approach which is to be followed

#2

A simple approach would be to simply make two arrays of stacks and solve as guided. We can precompute the primes using sieve to save time. This approach will take a lot of space as the sizes of arrays will be size = q+1.

Better Approach

While this algorithm takes almost same time, it saves a lot of space.
If we look at our algorithm more closely , you will notice that at any point , we only need 3 stacks atmost.

  1. Stack S from which we are popping elements. This is equivalant to stack a[i-1] from the previous method.
  2. Stack A to which we will be pushing the elements in case they are not divisible by ith prime number. This is equivalant to stack a[i] from the previous method.
  3. Stack B to which we will be pushing the elements in case they are divisible by ith prime number. This is equivalant to stack b[i] from the previous method.

After each iteration , make S = A for the next iteration since for the next iteration we will be popping elements out from the stack that is currently A.

After each iteration , we pop and push all elements from B to a queue to maintain the order which would otherwise have been maintained by having different arrays of stack.

This approach requires a lot less space than the previous approach and is thus better.