Se ho immaginato bene un algoritmo migliore sarebbe:

num1 e num2

div = {...} array dei divisori di num1

ciclo per i che va da 0 a lunghezza di div
if(resto di (num2/div[i]) uguale a zero) num1 e num2 non sono primi tra loro!


Spero di essermi fatto capire...ho cercato di prescindere dal linguaggio!
Cmq in linea di massima è come hai detto tu, solo con un solo array a con meno verifiche

Ciao