Smallest subarray problem


Say you have an array of integers like [1, 2, 3, 4, 5, 6], the problem is to find the smallest way to break up the array into sub-arrays where each sub-array satisfies the following requirement:

  • sub-array.first_integer and sub-array.last_integer must have a common divisor that is not 1.

So for [1, 2, 3, 4, 5, 6] the answer would be 2, because you can break it up like [1] and [2, 3, 4, 5, 6], where 2 and 6 have a common divisor of 2 (which is > 1 so it meets the requirement).

You can assume the array can be huge but the numbers are not too big. Is there a way to do this in n or n*log(n) time? I think with dp and caching n^2 is possible but not sure how to do it faster.