Подільність
Подільність — фундаментальна властивість натуральних та цілих чисел. Число 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 (кожне друге, починаючи з 22 = 4):
2 3 5 7 9 11 13 15 17 19
Наступне невикреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з 32 = 9):
2 3 5 7 11 13 17 19
Наступне невикреслене число 5 — просте. Викреслимо всі числа кратні 5 (кожне п’яте, починаючи з 52 = 25). І т. д.
Необхідно викреслити кратні для всіх простих чисел p, для яких p2<=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.
