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

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

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

Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N.

1.   Перше просте число - два. Викреслимо всі числа більші двох, які діляться на два (4, 6, 8 …).

2.   Наступне число, яке залишилося незакресленим (три), є простим. Викреслюємо всі числа більші трьох та кратні трьом (6, 9 …).

3.   Наступне незакреслене число (п'ять) є простим. Викреслимо всі числа більші п'яти та кратні п'яти (10, 15, 20, 25 …).

4.   Повторюємо операцію поки не буде досягнуто число N:

·         Наступне незакреслене число є простим. Викреслимо всі числа більші нього та кратні йому.

Числа, які залишилися незакресленими після цієї процедури - прості^[1].

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

Дружні числа

Дружні числа

Парні та непарні натуральні числа

Натуральні числа

Натуральні числа 1,2,3,… - це числа, що використовуються для рахування предметів або для вказування порядкового номера того чи іншого предмета серед однорідних предметів. Будь-яке натуральне число можна записати за допомогою десяти арабських цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Число 0 не є натуральним числом.Для читання натуральних чисел їх розбивають, починаючи справа, на групи по три цифри в кожній. Три перші цифри праворуч складають клас одиниць, три наступні – клас тисяч, потім йдуть класи мільйонів, мільярдів і т.д. Кожна із цифр класу називається його розрядом.
Із двох натуральних чисел менше те, яке при підрахунку називають раніше. Наприклад, число 8 менше від 12 (записують так: 8 < 12). Коли одне число більше другого, це записують так: 386 > 99.

Найменше натуральне число – 1.
Найбільшого натурального числа не існує.
Множину натуральних чисел позначають символом N.

Дії над натуральними числами

Додавання

а + b = b + а
(а + b) + с = а + (b + с)
а + 0 = 0 + а = а
Як правило, додавання виконується «стовпчиком»:

Віднімання – операція, обернена до додавання.
Якщо в + с = а, то

Якщо а = в, то а - b = а – а = 0
(а + b) – с = (а - с) + b
а – (b + с) = (а - b) – с
а + (b – с) = (а + b) – с
а – (b - с) = а – b + с
При відніманні результат зручно знаходити «стовпчиком»:

Множення


а ∙ b = b ∙ а
а ∙ b ∙ с = а ∙ (b ∙ с)
(а + b) ∙ с= а ∙ с + b ∙ с
(а – b) ∙ с = а ∙ с – b ∙ с
а ∙ 1 = 1 ∙ а = а
а ∙ 0 = 0 ∙ а = 0
0 ∙ 0 = 0
1 ∙ 1 = 1
Множення краще виконувати «стовпчиком»:

Ділення – операція, обернена до множення.
Якщо b ∙ с = а, то

а : 1 = a
a : a = 1, a ≠ 0
0 : a = 0, a ≠ 0

(а ∙ b) : c = (a :c) ∙ b
(а ∙ b) : c = (b :c) ∙ a
(a ∙ b) : c = a : (b ∙ c)
Ділення краще виконувати способом «кута»

Подільність натуральних чисел

Дільником натурального числа а називають натуральне число n, на яке а ділиться націло. Наприклад, дільниками числа 12 є числа 1,2,3,4,6,12. Число 1 є дільником будь-якого натурального числа
Кратним натурального числа a називають натуральне число, яке ділиться на a націло. Наприклад, кратними числа 6 є числа 6, 12, 18,…. Числа 0, 2, 4, 6, 8,… називають парними, а числа 1, 3, 5, 7, 9… - непарними.
На 2 діляться числа, остання цифра яких парна.
На 3 діляться числа, сума цифр яких ділиться на 3.
На 5 діляться числа, у яких остання цифра 5 або 0.
На 9 діляться числа, сума цифр яких ділиться на 9.
На 10 діляться числа, у яких остання цифра 0.
Ділення натурального числа а на натуральне число b (a > b) може бути як націло, так і з остачею q. Наприклад, при діленні числа 26 на число 8 одержуємо 26 = 8 ∙ 3 + 2, де 3 – частка, 2 – остача. Завжди q < b.
Натуральне число називається простим якщо воно не має інших дільників, крім одиниці і самого себе. Наприклад, числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 – прості.
Натуральне число називають складеним, якщо воно має хоча б один дільник, відмінний від одиниці і самого себе. Наприклад, це числа 4, 9, 14, 25.
Кожне складене число n можна розкласти на прості множники. Наприклад,


Один із можливих способів розкладу:

Найбільше натуральне число, на яке ділиться без остачі числа a і b називають найбільшим спільним дільником цих чисел: НСД (a, b). Наприклад, НСД (18,15) = 3
Для знаходження НСД декількох натуральних чисел, треба:

1. розкласти їх на прості множники;
2. виявити спільні множники;
3. знайти добуток цих множників;

Наприклад: знайти НСД (160, 240)


НСД (160, 240) = 24∙5 = 16∙5 = 80
Найменшим спільним кратним натуральних чисел a i b називають найменше натуральне число, яке кратне числам a i b: НСК (a, b). Наприклад, НСК (9, 12)= 36
Щоб знайти НСК декількох натуральних чисел, треба:

1. розкласти їх на прості множники;
2. дописати до множників одного із чисел ті множники з розкладу інших чисел, яких немає в першому;
3. знайти добуток одержаних множників.

Наприклад: Знайти НСК (160, 240)


НСК (160, 240) = 25∙5∙3= 480

Числові вирази і числові рівності

Запис, у якому числа з`єднані знаками дій, називають числовим виразом.
Наприклад, 10∙3+4; (60-2∙5):10.
Записи, у яких знаком рівності поєднано два числових вирази, називають числовими рівностями.Рівність має ліву і праву частини.

Порядок виконання арифметичних дій

Додавання і віднімання чисел називають діями першого ступеня, а множення і ділення чисел – діями другого ступеня.
Якщо числовий вираз містить дії тільки одного ступеня, то їх виконують по порядку зліва направо.
Якщо ці вирази містять дії тільки першого і другого ступенів, то спочатку виконують дії другого ступеня, а потім – дії першого ступеня.
Якщо у виразі є дужки, то спочатку виконують дії в дужках.
Наприклад, 36: (10-4)+3∙5= 36:6+15 = 6+15 = 21.

Далі...