Математика и числа

if Odd (Number) then 
  writeln (Number, ' нечётно')
else
  writeln (Number, ' чётно');

if Number mod 3 = 0 then
  writeln (Number, ' делится на 3 без остатка');

Делиться без остатка - означает кратность.

(НОД, англ. Greatest Common Divisor)

{ Евклид (Euclidus) }
function GCD (A: integer;  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;

(НОК, англ. Least Common Multiplier)

function LCM (A: integer;  B: integer): integer; 
begin
     LCM := a * b div GCD (a, b)
end;

Для целых чисел

function Power(Base, N: integer): longint;
{ Base - основание , N - степень }
var
   Result: longint;
   i: word;
begin
   Result := 1; { придаём начальное значение }
   for i := 1 to N do
     Result := Result * Base;
 
   Power := Result;
end;

Для вещественных чисел

Возвести A в степень N. Ограничения: [COLOR=red]только для A > 0[/COLOR]

function PowerExp (A, N: real): real;
begin
   if A > 0 then
     PowerExp := Exp ( N * Ln (A) )
   else 
     PowerExp := 0;
end;

function Factorial(N: word): longint;
var
   Result: longint;
   i: word;
begin
   Result := 1;
   for i := 1 to N do 
     Result := Result * N;
 
   Power := Result;
end;

С использованием рекурсии

function Factorial (N: word): longint;
begin
   if N = 0 then
     Factorial := 1 
   else 
     Factorial := N * Factorial (N - 1);
end;

Round - Округляет значение вещественного типа до значения целого типа, округляя. Trunc - Округляет значение вещественного типа до значения целого типа, отбрасывая дробную часть. Frac - Возвращает дробную часть аргумента. Int - Возвращает целую часть аргумента.

   var
       r : real;
     begin
       r := Round ( 123.456);  {    123 }
       r := Round ( 123.778);  {    124 }
       r := Trunc ( 123.456);  {    123 }
       r := Trunc (-123.778);  {   -123 }
       r := Frac  ( 123.456);  {  0.456 }
       r := Int   ( 123.456);  {  123.0 }
       r := Int   (-123.456);  { -123.0 }
     end.

Процедура Randomize - инициализирует генератор чисел. Функция Random (N) выдает целочисленные значения в диапазоне от 0 до N-1 ! Например, чтобы сгенерировать число X в диапазоне -N..N , пишем так:

  Randomize;
  X := Random (N + 1) - 2 * N;

Если не написать сначала Randomize; , то будут генерироваться одни и те же числа.

function isPrime(X: word): boolean;
var
i: integer;
Begin
     isPrime:=false;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     while i <= sqrt(x) do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
 
     isPrime:=true;
End;

procedure Factorization(x: word);
var i: word;
 
 procedure DivX; { делим на простое число, пока делится без остатка }
 begin
      while (x>1) and (x mod i = 0) do
      begin
           write(i:4);
           x:= x div i;
      end;
 end;
 
begin
     i:=2;
     DivX;
     i:=3;
     while (i < x div 2) do
     begin
           DivX;
           inc(i,2); { <=> i:=i+2; только нечётные числа }
     end;
     if x>1 then writeln(x:4);
end;

VAR p,q,qmax:integer;
    d, r, min: real;
BEGIN
   write('r, qmax=');
   readln(r, qmax); { r - не целое число, qmax - кол-во итераций (циклов) }
   p:=0; q:=1; min:=r;
   REPEAT
     IF p / q < r
          THEN inc(p)
          ELSE inc(q);
     d:=abs(r-p/q);
     IF d < min THEN
     BEGIN
          min:=d;
          writeln(p:7,'/',q)
     END
   UNTIL (q >= qmax) OR (d = 0);
   readln;
END.

FUNCTION IsBitOn (n: word; b : BYTE): BOOLEAN; { Проверяем, установлен ли бит }
BEGIN 
     isBitOn:=((n SHR b) AND 1) = 1
END;
 
PROCEDURE SetBitOn (VAR n: Word; b: BYTE); { Устанавливаем бит }
BEGIN
     N:= N OR (1 SHL b)
END;
 
PROCEDURE XORBit (VAR n: Word; b: BYTE); { Переключаем бит }
BEGIN
     N:= N XOR (1 SHL b)
END;

Var X : Integer;
Begin
 X:=12345;
 Writeln('Число состоит из таких цифр:');
 While X <> 0 Do
  Begin
   Writeln(X Mod 10);
   X:=X Div 10;
  End;
End.

Как известно, опрерации умножения и деления занимаю много машинного времени. Если требуется скорость, то целесообразно использовать логические сдвиги:

i:=i shl 1; { i:=i * 2^1}
i:=i shl 2; { i:=i * 2^2}
{и т.д.}
i:=i shr 1; { i:=i div 2^1}
i:=i shr 2; { i:=i div 2^2}
{и т.д.}

Примечание: корректно работает только с целыми беззнаковыми типами (word, byte…)! Если производить эти операции со знаковыми типами, то бит знака тоже сдвигается и в результате число может поменять свой знак!

В методе, описанном ранее, количество проверок пропорционально sqrt(N), т.е. для разложение числа порядка 10¹² потребуется около 10⁶ операций, причем используется деление! Существуют методы поиска делителей, которые справляются со своей задачей намного быстрее (без операций деления). В методе Ферма предполагается, что N - нечетное число, причем N = uv. Попробуем подобрать такие числа X и Y, что будет выполняться: N = p² - q². Обозначим u = (p + q) / 2 и v = (p - q) / 2. Будем пытаться приблизить числа p и q с разных сторон, чтобы выполнялось N = p² - q². Итак, сам алгоритм:

• Присвоим x = 2 * trunc(sqrt(N)) + 1, y = 1, r = sqr(trunc(sqrt(N))) - N (во время выполнения алгоритма числа x, y и r будут соответствовать 2p + 1, 2q + 1 и p² - q² - N)
• Если r = 0, то выполнение алгоритма заканчивается. Имеем N = ((x-y)/2)((x+y-2)/2) и (x-y)/2 - наибольши делитель числа N.
• Присвоить r = r + x, x = x + 2 (шаг по x)
• Присовить r = r - y, y = y - 2 (шаг по y). Делать этот шаг, пока r > 0.
• Перейти к проверке r = 0

Так как все действия алгоритма - это сложения и вычитания, то они на компьютере выполняются очень быстро. В результате работы алгоритма будет получено одно число - наибольший делитель числа N. Замечание: данный алгоритм лучше использовать для поиска больших делителей, нежели для маленьких!

{$N+, E+}
 
function FermaFactorization (N : Comp) : Comp;
 
var
  X, Y, R, Z, ZZ : Comp;
 
begin
 Z := Sqrt(N);
 ZZ := Trunc (Z);
 X := 2 * ZZ + 1;
 Y := 1;
 R := Sqr (ZZ) - N;
 while (R <> 0) do
  begin
   R := R + X;
   X := X + 2;
   repeat
    R := R - Y;
    Y := Y + 2;
   until R <= 0;
  end;
 FermaFactorization := (X - Y) / 2;
end;
 
begin
 Writeln (FermaFactorization(917979909) : 0 : 0);
end.