The problem asks us to find the largest subarray where all the numbers are pairwise co-prime. This means we need the largest subarray where each prime factor occurs only in one number. So for each prime factor of a number we can keep track of index of next number where it occurs as factor. Store the values in a new array.

( Consider the example n = 6 and A = {6, 7, 25, 13, 9, 21}. For number 6 (having prime factors 2 and 3), create store the index of the next number where the prime factors occurs. 2 occurs nowhere but 3 occurs in 9. So store for 6, max{5 (index of 9), 7 (since 2 occurs nowhere)}. That is for each number in A, the corresponding value is the minimum index (greater than current number's index) of the number whose gcd with current number is not 1. Do the same process for each number in A. Create a new array of values. The new 'next' array will look like B = {5, 6, 7, 7, 6, 7} )

After creating the new array, we use DP with dp[i] as length of the longest subarray starting from index i. Its not difficult to see that dp[i] = min {B[j]} for i < j <= n. So the answer is max {dp[1]} for 1 <= i <= n