Теория чисел

Есть несколько задач, которые требуют знания из теории чисел. Например, нахождение простых чисел, разложение на простые множители, деление с остатком, НОД и НОК и т.д. Некоторые из них мы разбирали - это простые числа. Рассмотрим другие.
Разложение числа на простые множители.
Например, число 153 = 3*51=3*3*17=3^2 * 17^1.
Итак, нам нужно определить на каждом шаге первое простое число, которое является делителем данного числа. Из теории чисел: наименьший собственный делитель числа N всегда будет простым. Для поиска первого простого делителя числа N воспользуемся следующей функцией:

function simple(n:integer):integer;

var a:integer;

begin

  a:=2;

  while sqr(a)<=n do begin

    if n mod a = 0 then begin simple:=a; exit; end;

    a:=a+1;

  end;

  simple:=n;

end;

var n,a:integer;

begin

  readln(n);

  while n > 1 do

  begin

     a := simple(n);

     n := n div a;

     writeln(a);

  end;

end.

Иногда требуется вывести не все множители (а они иногда повторяются), а только само число и его степень.

var n,a,k:integer;

begin

  readln(n);

  while n > 1 do

  begin

     a := simple(n);

     k:=0;

    while n mod a = 0 do begin

        n := n div a;

        k:=k+1;

     end;

     writeln(a, '^', k);

  end;

end.

Теперь попробуем найти все простые делители N!=1*2*3*...*N.

Пусть N=10, тогда 10!=1*2*3*4*5*6*7*8*9*10. Видно, что степени 2 2=2^1

4=2^2

6=3*2^1

8=2^3

10=5*2^1

Итого 1+2+1+3+1=8. 

Если разделим 10! на 2^1, то получим 5 вхождений (их можно считать так 10 div 2 = 5). Останется (1-1)+(2-1)+(1-1)+(3-1)+(1-1)=0+1+0+2+0=3 степени двойки. Из них 2 раза входит 2^2 (10 div 4 = 2) и один раз 2^3 (10 div 8 = 1). Так делаем для всех простых чисел:

если p - простое, то k = n div p +n div p^2 + n div p^3 +...

function simple(n:integer):boolean;
var i:integer;
begin
  simple:=true;
  if (n mod 2 = 0) and (n<>2) then simple:=false;
  for i:=2 to round(sqrt(n)) do begin
    if i mod 2 = 0 then continue;
    if n mod i = 0 then begin simple:=false; exit; end;
  end;
end;

                  

var i,n,p,k:integer;

begin

read(n);

for i:=2 to n do

  if simple(i) then begin

  p:=i; k:=0;

  while n div p >0 do begin k:=k+ n div p; p:=p*i; end;

  writeln(i,'^',k);

  end;

end.

Деление с остатком. Если даны два натуральных числа P и Q, то можно поделить P на Q с остатком  R  и частным от деления T. Тогда P=T*Q+R. Остатки от деления на одно и то же число можно складывать и умножать:

(P1+P2) mod Q = (P1 mod Q +P2 mod Q) mod Q

(P1*P2) mod Q = ((P1 mod Q )*(P2 mod Q)) mod Q

Пусть заданы два числа N и M. Необходимо найти остаток от деления числа N! на M. Используя выше приведенное условие получим следующий алгоритм решения задачи:

var n,m,t:integer;

begin

  read(n,m);

  t:=1;

  for I:=1 to n do

    t: = (t*i)mod m;

  write(t);

end.

Перейдем к следующей задаче: нахождение НОД (наибольший общий делитель) и НОК (наименьшее общее кратное). Решается такая задача с помощью алгоритма Евклида для двух натуральных чисел а и b:

пока a<>b

   если a<b то b:=a-b

     иначе если a>b то a:=a-b;

Например, НОД(16, 12)

a=16,  b=12

a<>b? да

a<b? нет

a>b? да

a:=a-b=16-12=4

a<>b? да

a<b? да

b:=b-a=12-4=8

a<>b? да

a<b? да

b:=b-a=8-4=4

a<>b? нет

НОД=4

Вычитание можно заменить взятие остатка. Тогда программа имеет вид:

var a,b,nod:integer;

begin

  read(a,b);

  while a<>b do

    if a<b then b:=b mod a

       else if a>b then a:=a mod b;

  nod:=a;

  write(nod);

end.

Но можно написать программу без условий и оформить в виде функции, при этом нужно учесть, что a>b:

function nod(a,b:integer):integer;

var r:integer;

begin

  if b>a then nod:=nod (b,a) else

  begin

  while b<>0 do

   begin

      r:=a mod b;

      a:=b;

      b:=r;

   end;

   nod:=a;

   end;

end;

var a,b:integer;

begin

  read(a,b);write(nod(a,b));

end.

Для нахождения НОК(a,b) воспользуемся формулой НОК(a,b)=a*b/НОД(a,b).

Если нужно найти НОД (или НОК) нескольких чисел, то последовательно находим

НОД( а1, а2, а3, а4) = НОД(НОД(НОД(а1, а2), а3), а4).