Как написать программу? Даны целые числа p и q. Найти делители взаемно простые делители q с числом p.

Программу нужно писать ручками с привлечением головы.
Порядок применения руки/голова зависит от того, пишешь сам или сдираешь чужое.

Если требуется найти наибольший общий делитель двух чисел, то смотри "Алгоритм Евклида".
Если требуется перечислить ВСЕ общие простые делители, то сначала применяется алгоритм Евклида, а затем находятся все простые делители получившегося числа.

Задача о нахождении простых делителей числа А быстрого решения не имеет: нужно просто делить на все простые числа, меньшие или равные корень (А) и выводить подошедшие. Сложность в том, как найти следующее простое число.. . Поэтому поступают проще: сначала пытаются делить на 2, а потом на все нечетные числа до корень (А) .

Кстати, если А удалось разделить на число К, то дальше делители можно искать уже у частного А/К. При этом начинать проверку нужно не с 2, а уже с К, так как на всё меньшее К мы уже делили. В момент замены частного ограничитель корень (А) также меняется на корень (А/К)