In my answer I will assume that all numbers are at most $M$ big, i.e. $A[i] \le M$.
First some comments about your both approaches.
Computing the GCD takes $O(\log M)$ time. So your first approach is actually $O(N^2 \log M)$.
I also don't think that your second approach is actually better than $O(N^2)$. For instance assume if all the numbers of the first half of the array are equal. Then for each of those numbers you have at least $\Theta(N)$ effort for each divisor of $N$. Which means that the complexity for such a test case is something like $O(N^2 \sqrt M)$.
Let's first discuss a very trivial (but slower) dynamic programming solution, on which I will later base a better one.
Let's define the function $f$ as $f(i)$ is the smallest number of subarrays in which you can split the prefix of size $i$ of the array (the first $i$ numbers). Also let $f(i) := \infty$ if it is not possible to split the array, and $f(0) := 0$.
It's easy to see, that you can compute $f(i)$ using the recursion:
$$f(i) = \min_{\substack{1 \le j \le i\\ \gcd(A[i], A[j]) > 1}} f(j-1) + 1$$
This formula is very trivially to implement together with dynamic programming, and will have the complexity $O(N^2 \log M)$.
f(0) = 0
for i = 1 to N:
f(i) = infinity
for j = 1 to i:
if gcd(A[i], A[j]) > 1:
f(i) = min(f(i), f(j-1)) + 1
print f(N)
Now to a better approach. We need two mathematical facts that will help us:
- If two numbers have a common divisor greater than one, then they have a common prime factor.
- A number $\le M$ has at most $\log M$ prime factors.
Let the set of prime factors of $x$ be $P(x)$.
Then we can also rewrite the recursion for $f$ as:
$$f(i) = \min_{p \in P(A[i])} \left( \min_{\substack{1 \le j \le i\\ p ~|~ A[j]}} f(j-1) \right) + 1$$
In other word, if $A[i] = 20 = 2^2 \cdot 5$, then we look for all previous numbers who are divisible by 2, and take the minimum of $f(j-1)$, and for all previous numbers who are divisible by $5$ and take the minimum of $f(j-1)$. The actual optimal value $f(i)$ will one more than the minimum of both.
If we define $g(p, i)$ as the minimum of $f(j-1)$ with $p ~|~ A[j]$ and $1 \le j \le i$, then the formula simplifies to:
$$f(i) = \min_{p \in P(A[i])} g(p, i) + 1$$
We can actually apply some sort of dynamic programming also to the function $g$.
We store the values in a hash table.
First we initialize the function for every possible prime factor with $g(p) = \infty$, and whenever a $f(j-1)$ changes, we update $g(p)$ for every $p \in P(A[j])$.
This means, after we update $f(i)$, we only need to update $O(\log M)$ different values of $g$.
This gives us the following algorithm:
# initialize g
for all p:
g(p) = infinity
# set the first value f(0)
f(0) = 0
# update g
for p in P(A[1]):
g(p) = min(g(p), f(0))
for i = 1 to N:
# first compute f(i)
f(i) = infinity
for p in P(A[i]):
f(i) = min(f(i), g(p)) + 1
# and then update g
if i < N:
for p in P(A[i+1]):
g(p) = min(g(p), f(i))
print f(N)
It's easy to see that this algorithm runs in $O(N \log M)$ time.
A shorter variation, but with the exact same approach and complexity, would also be:
for all p:
g(p) = infinity
f(0) = 0
for i = 1 to N:
f(i) = infinity
for p in P(A[i]):
g(p) = min(g(p), f(i-1))
f(i) = min(f(i), g(p)) + 1
print f(N)
The only thing to discuss is, how we get the prime factorization of each number.
There are loads of different approaches.
For instance if $M$ is not too big, you can compute the Sieve of Eratosthenes in $O(M \log M)$ and during the computation store a prime factor for each number $\le M$. This allows to compute the prime factorization of each number in $O(\log M)$.
Another option would be just to compute the prime factors on the fly, which would give take additionally $O(N \sqrt{M}$) time if you use the typical trial division until square root algorithm.
