Базовые Алгоритмы Теории Чисел

В этом видео поговорим про базовые алгоритмы теории чисел. Узнаем как искать делители, как факторизовать число, про решето Эратосфена, про алгоритм Евклида, про модульную арифметику и алгоритм быстрого возведения в степень.

Домашку можно найти тут:
https://t.me/wilcodit_school/195

00:00:00 Что будет
00:00:25 Что такое делитель
00:01:23 Поиск делителей за О(n)
00:03:04 Парные делители
00:06:03 Поиск делителей за O(sqrt(n))
00:08:55 Что такое простое число
00:09:47 Проверка на простоту
00:13:27 Основная теорема арифметики
00:14:27 Факторизация числа
00:29:11 Все простые до n за О(n*sqrt(n))
00:31:23 Решето Эратосфена за O(n log log n)
00:40:26 НОД (gcd)
00:43:32 Алгоритм Евклида O(log n)
00:51:00 Интересная задача на НОД
00:58:32 Деление отрицательных чисел
01:06:51 НОК (lcm)
01:12:13 Сравнения по модулю
01:18:25 Арифметика остатков
01:27:43 Деление по модулю
01:31:05 Обратное число по модулю
01:40:42 Алгоритм быстрого возведения в степень О(log n)
01:50:03 Цикличность остатков