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