Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1. Примеры: 14 и 25 взаимно просты, а 15 и 25 не взаимно просты (у них имеется общий делитель 5).
Сама программа с результатом вычисления
Сам код для копирования и проверки.
var p,q,i,s,j,k: integer;
a:array[1..100] of integer;
begin
cls;
s:=1;
p:=random(10000);
q:=random(10000);
writeln('p=',p,' q=',q);
for i:=2 to round(sqr(q))+1 do begin
if q mod i=0 then begin
inc(k); a[k]:=i;
for j:=2 to round(sqr(i))+1 do begin
if (p mod j=0) and (i mod j=0) then s:=0;
end;
if s=1 then writeln('Делитель числа ',q,': ',i,' -взаимно простое число с числом ',p);
s:=1;
end;
end;
writeln('Все делители числа q=',q);
for i:=1 to k do write(' ',a);
end.
Перебрать все числа от 2 до корня из q, если это делитель q - найти НОД этого числа и p, если 1 - вывести.
Гугли "алгоритм Эвклида"