Pascal:Целочисленная арифметика

Материал из Synset

Содержание 1 Целочисленная арифметика(описание) 2 Функция для определения принадлежности числа к простым: 3 Наибольший общий делитель: 4 Наименьшее общее кратное

Целочисленная арифметика(описание)

В данном разделе представлены описания и реализация программ которые могут быть полезны в решении задач с целочисленной арифметикой.

Функция для определения принадлежности числа к простым:

Function Prime(n:longint):boolean;
var
   p,i:longint;
   b:boolean;
begin
   b:=true;
   if (n=1) or ((n>3) and (n mod 2=0)) then
   b:=false
   else
   begin
      p:=trunc(sqrt(n));
      i:=3;
      While (i<=p) and b do
      begin
         b:=n mod i<>0;
         i:=i+2;
      end;
   end;
   Prime:=b;
end; 

Наибольший общий делитель:

Function GCD(a,b:longint):longint;
var
   x,y:longint;
begin
   x:=a;
   y:=b;
   While x<>y do
      if x>y then x:=x-y
      else y:=y-x;
   GCD:=x;
end;

Наименьшее общее кратное

Для нахождения НОК удобно использовать следующее свойство: для любых натуральных чисел a и b верно равенство НОД(a,b)*НОК(a,b)=a*b , откуда получаем, что НОК(a,b)=a*b/НОД(a,b).

program SCM;

Function GCD(a,b:longint):longint;
var
   x,y:longint;
begin
   x:=a;
   y:=b;
   While x<>y do
      if x>y then x:=x-y
      else y:=y-x;
   GCD:=x;
end;

var
   a,b:integer;
begin
   Read(a,b);
   WriteLn(f2,a*b div GCD(A,B));
   ReadLn;
end.