Подільність

Подільність — фундаментальна властивість натуральних та цілих чисел. Число a ділиться на b, відповідно, число b є дільником a, якщо частка  — ціле число. Будь-яке натуральне число ділиться на одиницю і на себе. Якщо дане число не має інших дільників, то таке число називається простим, в іншому разі — складним

Таблиця подільності

Дільник	Умова подільності	Приклади
2	Остання цифра є парною (0, 2, 4, 6, або 8).	1,294: 4 є парне.
3	Сума цифр повинна ділитися на 3.	405: 4 + 0 + 5 = 9. 9 ділиться на 3.
4	Якщо число, утворене двома останніми цифрами ділиться на 4.	2,092: 92 ділиться на 4.
7	Число розбивається на блоки по три цифри, починаючи з кінця. Число ділиться на 7, якщо різниця суми блоків, що стоять на парних місцях, і суми блоків, що стоять на непарних місцях, ділиться на 7.	2,911,272: - (2 + 272) + 911 = 637. 637 ділиться на 7.
	Якщо сума подвоєного числа без останніх двох цифр і останніх двох цифр ділиться на 7.	364: (3x2) + 64 = 70. 70 ділиться на 7
	Якщо сума числа без останньої цифри і останньої цифри, помноженої на 5, ділиться на 7.	364: 36 + (5x4) = 56. 56 ділиться на 7.
	Різниця між числом без останньої цифри і подвоєної останньої цифри повинна ділитись на 7.	364: 36 - (2x4) = 28. 28 ділиться на 7.
9	Сума всіх цифр повинна ділитись на 9.	2,880: 2 + 8 + 8 + 0 = 18. 18 ділиться на 9.
10	Остання цифра 0.	130: остання цифра 0.
11	Число розбивається на блоки по дві цифри, починаючи з кінця. Сума блоків повинна ділитись на 11.	627: 6 + 27 = 33. 33 ділиться на 11.
	Якщо різниця між числом без останньої цифри і останньою цифрою ділиться на 11.	627: 62 - 7 = 55. 55 ділиться на 11.
	Якщо сума цифр, що стоять на парних місцях відрізняється від суми цифр, що стоять на непарних місцях, починаючи з кінця, на число, що кратне 11.	182,919: (9 + 9 + 8) - (1 + 2 + 1) = 22.
13	Число ділиться на блоки по три цифри, починаючи з кінця. Сумуються блоки, що стоять на парних і непарних місцях. Різниця цих сум повинна ділитись на 13.	2,911,272: - (2 + 272) + 911 = 637. 637 ділиться на 13.
	До числа без останньої цифри додають останню цифру, помножену на 4. Утворене число повинне ділитись на 13.	338: 33 + (8x4) = 65. 65 ділиться на 13.
	Від числа без останньої цифри віднімають останню цифру, помножену на 9. Утворене число повинне ділитись на 13.	637: 63 - (7x9) = 0. 0 ділиться на 13.
17	Число без останніх двох цифр множать на 2 і додають число, утворене останніми двома цифрами. Результат повинен ділитись на 17.	187: - (1x2) + 87 = 85. 85 ділиться на 17.
	Від числа без останньої цифри віднімають останню цифру, помножену на 5. Результат повинен ділитись на 17.	85: -8 + (5x5) = 17.
19	До числа без останньої цифри додають подвоєну останню цифру. Результат повинен ділитись на 19.	437: 43 + (7x2) = 57. 57 ділиться на 19.

Просте число

Просте число  — це натуральне число, яке має рівно два натуральних дільника (лише 1 і саме число)

Послідовність простих чисел починається так:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 , 127, 131, 137, 139, 149, …

Решето Ератосфена

Решето Ератосфена в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа n, що був створений давньогрецьким математиком Ератосфеном. Він є попередником сучасного решета Аткіна, швидшого, але і складнішого алгоритму.

Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N2 -1. Потім в цьому ряду вискреслюються всі числа, які діляться на 2,3, 4 і так далі до N. Числа, які залишилися невикресленими після цієї процедури - прості.

Приклад для n = 20

Запишемо натуральні числа від 2 до 20 в рядок:

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

Перше число в рядку 2 — просте. Викреслимо всі числа кратні 2 (кожне друге, починаючи з 2² = 4):

  2   3  5  7  9  11  13  15  17  19

Наступне невикреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з 3² = 9):

  2   3  5  7  11  13  17  19

Наступне невикреслене число 5 — просте. Викреслимо всі числа кратні 5 (кожне п’яте, починаючи з 5² = 25). І т. д.

Необхідно викреслити кратні для всіх простих чисел p, для яких p²<=n. В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для n = 20 вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими.

Приклад 1. Перевірити чи число просте

Код Pascal

function isprime(n : integer) : boolean;

var

i, j : integer;

begin

if (2 = i) then

isprime := true

else begin

j := round(sqrt(n))+1;

for i := 2 to j do

if (n mod i = 0) then begin

isprime := false;

exit;

end;

isprime := true;

end;

end;

Розклад натуральних чисел на добуток простих

Основна теорема арифметики стверджує, що кожне натуральне число більше одиниці (1), можна представити як добуток простих чисел, причому, в єдиний спосіб з точністю до порядку множників. Таким чином, прості числа - це елементарні «будівельні блоки» натуральних чисел.

Представлення натурального числа у вигляді добутку простих називають розкладом на прості або факторизацією числа.

 

Приклад 2. Розклад натурального числа на добуток простих

Код Pascal

Uses CRT;

var

   i,N,j,Delitel,l,B,Chastnim:Integer;

   s,Result:string;

begin

    clrscr;

    Write('Vvedite N = '); Readln (N);

    Chastnim:=0;

    if N=1 then  Exit;

    B:=N;

    Delitel:=2;

    s:='';

    Repeat

     j:=0;

     for i:=1 to Delitel do

       if Delitel mod i=0 then j:=j+1;

     if j=2 then

     begin

        if B mod Delitel=0 then

         begin

          s:=s+'*'+inttostr(Delitel);

          Chastnim:=B div Delitel;

          while Chastnim mod Delitel=0 do

           begin

            s:=s+'*'+inttostr(Delitel);

            Chastnim:=Chastnim div Delitel;

            if Chastnim mod Delitel=0 then continue else break;

           end;

        end;

       end;

     inc(Delitel,1);

    until Delitel=N;  

    delete(s,1,1);

   Result:='='+s;

 Writeln (N,Result);

 Readln

end.

 

Найбільший спільний дільник

Найбільшим спільним дільником (НСД) двох цілих чисел a, b, принаймі одне з яких є відмінне від нуля, називаємо найбільше натуральне число, яке є дільником обох цих чисел. Позначаємо НСД(a, b), деколи (a, b), в англомовній літературі GCD(a, b). Означення можна – очевидним способом – узагальнити на довільну кількість аргументів.

Властивості•  НСД(a, b)= НСД(b, a) (перестановка аргументів не змінює НСД).

•          1<=НСД(a, b)<=min(|a|,|b|)

•          НСД(a, b, c, d) = НСД(НСД(a, b), НСД(c, d) )

•          НСД(a, b) =|ab|/НСК(a, b), де НСК(a, b) найменше спільне кратне чисел a, b.

 

Приклад 3. Знаходження НСД чисел

uses crt;

function Nod(a,b:integer):integer;{знаходження НСД 2 чисел}

begin

 while a<>b do

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

 Nod:=a;

end;

 var a:array[1..100] of integer;

    n,i:byte;

    k:integer;

begin

clrscr;

write('Введіть к-сть елементів n=');

readln(n);

writeln('Введіть елементи масиву: ');

for i:=1 to n do

 begin

  write('a[',i,']=');

  readln(a[i]);

 end;

clrscr;

writeln('Масив:');

for i:=1 to n do

write(a[i],' ');

writeln;

k:=Nod(a[1],a[2]);

for i:=3 to n do k:=nod(k,a[i]);

writeln('НСД елементів=',k);

readln

end.

 

Найменше спільне кратне

Найменше спільне кратне (НСК) двох цілих чисел a, b називаємо найменше натуральне число, яке є кратним обох цих чисел. Позначаємо НСК(a, b), в англомовній літературі LCM(a, b). Отже НСК(a, b) є найменшим натуральним числом, яке ділиться без залишку на обидва числа a, b. Означення можна – очевидним способом – узагальнити на довільну кількість аргументів.

Властивості•  НСК(a, b)= НСК(b, a) (перестановка аргументів не змінює НСК).

•          НСК(a, b, c, d) = НСК(НСК(a, b), НСК(c, d) )

•          НСК(a, b) =|ab|/НСД(a, b), де НСД(a, b) найбільший спільний дільник чисел a, b.

 

Приклад 4. Знаходження НСК чисел

Код Pascal

uses crt;

function NOD(x,y:integer):integer;

Begin

If x<>0 then NOD:=NOD(y mod x,x) else NOD:=y;

End;

function NOK(x,y:integer):integer;

Begin

NOK:=(x div NOD (x,y))*y;

end;

var a:array[1..100] of integer;

    n,i:byte;

    k:integer;

begin

clrscr;

write('Введіть к-сть елементів n=');

readln(n);

writeln('Введіть елементи масиву: ');

for i:=1 to n do

 begin

  write('a[',i,']=');

  readln(a[i]);

 end;

clrscr;

writeln('Масив:');

for i:=1 to n do

write(a[i],' ');

writeln;

k:=NOK(a[1],a[2]);

for i:=3 to n do k:=NOK(k,a[i]);

writeln('НСК елементів=',k);

readln

end.

 

Взаємно прості числа — натуральні або цілі числа, які не мають спільних дільників більших за 1, або, інакше кажучи, якщо їх найбільший спільний дільник дорівнює 1. Таким чином, 2 і 3 — взаємно прості, а 2 і 4 — ні (діляться на 2). Будь-яке натуральне число взаємно просте з 1. Якщо p — просте, а n — довільне ціле число, то вони взаємно прості тоді і тільки тоді, коли n не ділиться на p.

 

Взаємна простота великих чисел може бути перевірена і доведена чи спростована за допомогою алгоритму Евкліда.

Приклад 5. Визначити чи є задані числа взаємно простими

Код Pascal

uses crt;

var a,b:word;

function NOD(m,n:integer):integer;

begin

while m<>n do

if m>n then m:=m-n else n:=n-m;

NOD:=m;

end;

begin

clrscr;

write('a=');readln(a);

write('b=');readln(b);

writeln;

if NOD(a,b)=1 then write('Эти числа взаимно простые!')

else write('Эти числа не являются взаимно простыми!');

readln

end.

 

Досконалі числа

Досконале число — натуральне число, яке дорівнює сумі всіх своїх дільників. Всього їх знайдено 24.

 

Найменшим досконалим числом є число 6: 6=3+2+1, наступне досконале число — число 28: 28=14+7+4+2+1

Приклад 6. Знаходження досконалих чисел на заданому діапазоні

Код Pascal

Uses crt;

Var a,b,m:longint;

procedure sov(c,d:longint;var l:longint);

var j,i,s:longint;

begin

for i:=a to b do

begin

s:=0;

for j:=1 to i-1 do

if (i mod j)=0 then s:=s+j;

if s=i then writeln(i);

end;

end;

BEGIN

clrscr;

writeln('Введіть діапазон');

readln(a,b);

writeln('Досконалі числа в заданому діапазоні:');

sov(a,b,m);

readkey;

END.