We know that for any number N we can check all the divisors of N in sqrt(N) complexity. Basically we just need to go through all the divisors of N or M and check if it divides both N and M. we will take the minimum of such divisors except 1.
time complexity O(sqrt(N))