Функция НОД в программе.

[JellyFilled]

Вообще само задание звучит так: Даны 2 натуральных числа n и p, найти все натуральные числа меньшие n и взаимно простые с p.
Можете рассказать как работает функция NOD в программе, пожалуйста.

uses crt;
function NOD(m,n:integer):integer;
begin
  while m<>n do
  if m>n then m:=m-n else n:=n-m;
  NOD:=m;
end;
var n,p,i,k:integer;
begin
  clrscr;
  repeat
    write('Введите натуральное число n=');
    readln(n);
  until n>2;
  repeat
    write(Введите натуральное число  p=');
    readln(p);
  until p>1;
    writeln('Числа от 2 до ',n-1,',взаимно простые с ',p);
  for i:=1 to n-1 do
  if NOD(i,p)=1 then
    begin
      k:=1;
      write(i,' ')
      end;
    if k=0 then write('Нет чисел, взаимно простых с ',p);
    readln;
end.

[Stilet]

Наверное ищет наименьший общий делитель.
Механизм можно описать примерно так: Нужно подогнать два числа друг к другу, для чего постепенно эти числа взаимовычитаются друг из друга, пока не поравняются в одно число, которое и будет результатом
Т.е. допустим имеем числа 7 и 2
Из 7 вычитаем 2 = 5
Из 5 вычитаем 2 = 3
Из 3 вычитаем 2 = 1
Теперь уже 2 стало больше. Из 2 вычитаем 1 = 1.
Все. Вычитать больше нечего ибо 1 = 1 - возвращаем эту единицу.

[Serge_Bliznykov]

НОД - это НАИБОЛЬШИЙ общий делитель (см. вики).

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.[1] Пример: для чисел 70 и 105 наибольший общий делитель равен 35.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

function NOD(m,n:integer):integer;
begin
  while m<>n do
  if m>n then m:=m-n else n:=n-m;
  NOD:=m;
end;

begin
 WriteLn(NOD(70 , 105 )); // выведет 35
end.

[JellyFilled]

Сообщение от Serge_Bliznykov

НОД - это НАИБОЛЬШИЙ общий делитель (см. вики).

function NOD(m,n:integer):integer;
begin
  while m<>n do
  if m>n then m:=m-n else n:=n-m;
  NOD:=m;
end;

begin
 WriteLn(NOD(70 , 105 )); // выведет 35
end.

А можно вопрос по программе.
Вообщем

for i:=1 to n-1 do
  if NOD(i,p)=1 then

В этой строчке он предполагает, что i=m, а p=n, и если НОД равен 1, то записывает это число? (и я забыл, что начинается так for i:=2, а не 1)
А и всё же, почему в функции NOD'у присваивается именно значение m?

[Poma][a]

и всё же, почему в функции NOD'у присваивается именно значение m?

Можно присваивать и N и M.. Они равны.. Поэтому разницы нет..

В этой строчке он предполагает, что i=m, а p=n, и если НОД равен 1, то записывает это число?

Примерно так

[Serge_Bliznykov]

А и всё же, почему в функции NOD'у присваивается именно значение m?

конкрентно в данном алгоритме это совсем не важно.
если вы посмотрите на условие цикла:

  while m<>n do
  if m>n then m:=m-n else n:=n-m;
  NOD:=m;

то увидите, что цикл по вычитанию из большего меньшего будет выполняться до тех пор, пока m и n не станут равны друг другу.
поэтому, не нравится Вам NOD:=m;
пишите NOD:=n;
это тоже самое в данном случае

[JellyFilled]

Сообщение от Serge_Bliznykov

конкрентно в данном алгоритме это совсем не важно.
если вы посмотрите на условие цикла:

то увидите, что цикл по вычитанию из большего меньшего будет выполняться до тех пор, пока m и n не станут равны друг другу.
поэтому, не нравится Вам NOD:=m;
пишите NOD:=n;
это тоже самое в данном случае

Спасибо Вам.

Сообщение от Poma][a

Можно присваивать и N и M.. Они равны.. Поэтому разницы нет..

Примерно так

И Вам.

[Serge_Bliznykov]

кстати, для коллекции, вот ещё одна функция, которая делает то же самое, только чуть по другому:

function GCD(a, b: Integer): Integer;
begin
  while (a<>0) and (b<>0) do 
      if a>b then a:=a mod b else b:=b mod a;
  GCD:=a+b;
end;