====== Математика и числа ======
==== Чётность/нечётность чисел ====
<code pascal>
if Odd (Number) then 
  writeln (Number, ' нечётно')
else
  writeln (Number, ' чётно');
</code>

==== Делимость (кратность) чисел ====
<code pascal>if Number mod 3 = 0 then
  writeln (Number, ' делится на 3 без остатка');</code>Делиться без остатка - означает __кратность__.

==== Наибольший Общий Делитель ====
(НОД, англ. Greatest Common Divisor)
<code pascal>{ Евклид (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;</code>

==== Наименьшее Общее Кратное ==== 
(НОК, англ. Least Common Multiplier)
<code pascal>function LCM (A: integer;  B: integer): integer; 
begin
     LCM := a * b div GCD (a, b)
end;</code>

==== Степень ====
//Для целых чисел//
<code pascal>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;</code>

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

Возвести //A// в степень //N//. Ограничения: [COLOR=red]только для //A > 0//[/COLOR]
<code pascal>function PowerExp (A, N: real): real;
begin
   if A > 0 then
     PowerExp := Exp ( N * Ln (A) )
   else 
     PowerExp := 0;
end;</code>

==== Факториал ====
<code pascal>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;</code>

//С использованием рекурсии//
<code pascal>function Factorial (N: word): longint;
begin
   if N = 0 then
     Factorial := 1 
   else 
     Factorial := N * Factorial (N - 1);
end;</code>
==== Вещественный и целый типы ====
**//Round//** - Округляет значение вещественного типа до значения целого типа, округляя.
**//Trunc//** - Округляет значение вещественного типа до значения целого типа, отбрасывая дробную часть.
**//Frac//** - Возвращает дробную часть аргумента.
**//Int//** - Возвращает целую часть аргумента.
<code pascal>   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.</code>

==== Случайные числа ====
Процедура **Randomize** - инициализирует генератор чисел.
Функция **Random (N)** выдает //целочисленные// значения в диапазоне от **//0//** до **//N-1//** !
Например, чтобы сгенерировать число X в диапазоне **//-N..N//** , пишем так:
<code pascal>  Randomize;
  X := Random (N + 1) - 2 * N;</code>
Если не написать сначала **Randomize;** , то будут генерироваться одни и те же числа.

==== Как проверить простое ли число? ====
<code pascal>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;</code>

==== Разложение числа на множители ====
<code pascal>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;</code>
==== Приближённое представление числа в виде дроби ====
<code pascal>
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.</code>

==== Как работать с отдельными битами? ====
<code pascal>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;
</code>

==== Как узнать из каких цифр состоит целое число? ====
<code pascal>Var X : Integer;
Begin
 X:=12345;
 Writeln('Число состоит из таких цифр:');
 While X <> 0 Do
  Begin
   Writeln(X Mod 10);
   X:=X Div 10;
  End;
End.</code>

==== Как быстро делить/умножать числа на степень двойки ? ====

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

<code pascal>
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}
{и т.д.}
</code>

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

==== Более быстрое разложение числа на множители ==== 
В методе, описанном ранее, количество проверок пропорционально sqrt(N), т.е. для разложение числа порядка 10<sup>12</sup> потребуется около 10<sup>6</sup> операций, причем используется деление!
Существуют методы поиска делителей, которые справляются со своей задачей намного быстрее (без операций деления).
В методе Ферма предполагается, что N - нечетное число, причем N = uv. Попробуем подобрать такие числа X и Y, что будет выполняться:
N = p<sup>2</sup> - q<sup>2</sup>. Обозначим u = (p + q) / 2 и v = (p - q) / 2.
Будем пытаться приблизить числа p и q с разных сторон, чтобы выполнялось N = p<sup>2</sup> - q<sup>2</sup>.
Итак, сам алгоритм:
  * Присвоим x = 2 * trunc(sqrt(N)) + 1, y = 1, r = sqr(trunc(sqrt(N))) - N (во время выполнения алгоритма числа x, y и r будут соответствовать 2p + 1, 2q + 1 и p<sup>2</sup> - q<sup>2</sup> - 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. Замечание: данный алгоритм лучше использовать для поиска больших делителей, нежели для маленьких!

<code pascal>

{$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.
</code>