Сергей Копелиович: простые числа

Пятая лекция в рамках курса «Алгоритмы и структуры данных» на школе по практическому программированию и анализу данных от Питерской Вышки и компании JetBrains 2022.

Темы лекции:
– Список делителей для всех чисел от 1 до N
– Количество простых от 1 до N за O(N)
– Расширенный алгоритм Евклида
– Выбор min x больше 0 : ax mod m меньше b

Лектор: Сергей Копелиович, старший преподаватель департамента информатики Санкт-Петербургской школы физико-математических и компьютерных наук НИУ ВШЭ – Санкт-Петербург, золотой медалист IOI 2005, 2006 и ACM ICPC 2009.