program Prost7;

{$APPTYPE CONSOLE}

uses
  SysUtils;

//Программа для определения НОД и НОК для двух чисел. Попутно выводятся разложениия этих чисел на простые множители.

function Esy(N:integer):Boolean;      //Функция, определяющая, является ли число простым
var
P,k,i:integer;
begin
k:=0;

while P*P<N do                         //Определение целого корня из N
  begin
  P:=P+1;
  end;

N:=P;                                   //Вместо числа теперь будем использовать его корень

for i:=1 to N do                        //Счетчик делителей
       begin
             if(N mod i)>0 then
             k:=k+1;
       end;

if k+2=N then
   begin
        Esy:=True
   end
   else
   begin
        Esy:=False;
   end;
end;


                                                     // Вычисление НОД двух чисел
var
v,z,x,c,q,t,j,k,l,i,m,N,P,N2,P2:integer;
W1,NOK,W,P1,N1:extended;
A:array[1..1000000] of integer;   // хранение простых чисел, идущих до N
B1:array[1..1000000] of integer;  // хранение простых числен, на кот. P делится без остатка
A1:array[1..1000000] of integer;  // хранение простых числен, на кот. N делится без остатка
A2:array[1..1000000] of integer;  // разложение N на простые множители
B2:array[1..1000000] of integer;  // разложение P на простые множители
PN:array[1..1000000] of integer;   // общие простые множители N,P

label
GotoLabel;

begin
writeln('PROGRAMMA RABOTAET S NEOTRICATELNIMI ZNA4eNIYAMI P,N');
repeat
writeln;                                       //Задаем числа, для которых будем находить НОД u НОК
writeln('------------------------------');
write('N=');
readln(N2);
write('P=');
readln(P2);

if (N2=0) or (P2=0) then
begin
    writeln;
    writeln('vvodite zna4eniya otli4nie ot nulya');
    goto gotolabel;
end;

if N2<P2 then                //Упорядочим числа
   begin
       N:=P2;
       P:=N2;
   end
   else
   begin
       N:=N2;
       P:=P2;
   end;


if (N mod P)=0 then          //Простейший случай
begin
   writeln;
   writeln('NOD(P,N)=',P);
   writeln;
   writeln('NOK(P,N)=',N);
   goto gotolabel;
end;


m:=1;
for i:=2 to N do        //создание   вектора из простых чисел, идущих до N   (большего из чисел) A[1..m-1]
begin
    if ((i mod 10)-1=0) or ((i mod 10)-3=0) or ((i mod 10)-7=0) or ((i mod 10)-9=0) or (i=2) or (i=5) then      //Оптимизация алгоритма - заведомо простые числа проверять не будем
         begin
            if (Esy(i)=True) then
                begin
                a[m]:=i;
                m:=m+1;
                end;
         end;
end;

                    //Разложение на простые множители числа N , P

//Нахождение простых чисел, на которое N делится без остатка
j:=1;
for k:=1 to m-1 do
begin
  if (N mod a[k])=0 then
      begin
      a1[j]:=a[k];          // Вектор A1[1..j-1] содержит в себе простые числа, на котороые делится N
      j:=j+1;
      end;
end;

//Нахождение простых чисел, на которое P делится без остатка
//Нет смысла делить P на простые числа, которые больше nего самого. они точно не будут его делителями

z:=1;
for k:=1 to m-1 do
begin
  if ((P mod a[k])=0) and (P>=a[k]) then     //небольшая оптимизация алгоритма
      begin
      b1[z]:=a[k];          // Вектор B1[1..z-1] содержит в себе простые числа, на котороые делится P
      z:=z+1;
      end;
end;

writeln;
writeln('Razlojenie bolshego 4isla');
writeln;

q:=1;
N1:=N;                      //Вектор A2[1..q-1] является разложением числа N на простые делители
for k:=1 to j-1 do          // сразу же выводим этот вектор
begin
while frac(N1/a1[k])=0 do
       begin
       a2[q]:=a1[k];
       write(q,'.  ');
       writeln(a2[q]);
       q:=q+1;
       N1:=N1/a1[k];
       end;
end;

Writeln;
Writeln('Razlojenie menshego 4isla');
writeln;

c:=1;
P1:=P;                      //Вектор B2[1..с-1] является разложением числа P на простые делители
for k:=1 to z-1 do          // сразу же выводим этот вектор
begin
while frac(P1/b1[k])=0 do
       begin
       b2[c]:=b1[k];
       write(c,'.  ');
       writeln(b2[c]);
       c:=c+1;
       P1:=P1/b1[k];
       end;
end;

         //Создание вектора из общих простых множителей чисел P , N
writeln;
writeln('obshie deliteli - ');
writeln;

v:=1;
for k:=1 to q-1 do              // PN[1..v-1] содержит в себе общие делители чисел P , N
begin
         for l:=1 to c-1 do
         begin
               if a2[k]=b2[l] then
                             begin
                                PN[v]:=b2[l];
                                writeln(v,'. ',PN[v]);
                                b2[l]:=0;                         //Зануляем в разложении на множетили числа, входящие в НОД
                                a2[k]:=0;
                                v:=v+1;
                                break
                              end;
         end;
end;

                     //Собственно, вычисление НОД для P,N , которое будет произведением всех членов вектора PN[1..v-1]
writeln;


W:=1;                  //Умножение элементов вектора PN др. на друга , получение НОД
for k:=1 to v-1 do
begin
W:=W*PN[k];
end;

W1:=1;                                  //Вычисление НОК

for L:=1 to c-1 do                //Перемножаем элементы, не вошедшие в НОД
begin
  if (b2[l]<>0) then
    begin                         //Для числа P
    W1:=W1*b2[l];
    end;
end;

for k:=1 to q-1 do
begin
   if (a2[k]<>0) then            //для числа N
   begin
   W1:=W1*a2[k];
   end;
end;

NOK:=W1*W;           // НОК явл-ся произведением НОД на произв. не вошедших в него членов


writeln('NOK(P,N)=',NOK);
writeln;
writeln('NOD(P,N)=',W);
Gotolabel:
until false;
end.