Числовые алгоритмы: Евклид, решето Эратосфена и диофантовы уравнения — тест

Наибольший общий делитель, простые числа и целочисленные уравнения — классика, с которой начинаются олимпиадные задачи и криптография. Набор проверяет, понимает ли ученик, почему работают алгоритм Евклида и решето Эратосфена, и умеет ли применять их к диофантовым уравнениям.

Какие темы охватывает набор

Алгоритм Евклида с вычитанием и с остатком, его усовершенствованная версия, находящая коэффициенты разложения НОД. Наименьшее общее кратное через НОД. Решето Эратосфена: почему вычёркивание начинают с квадрата простого и когда останавливаются. Проверка простоты перебором делителей до корня из числа. Разложение на простые множители. Линейные диофантовы уравнения, условие существования целых решений и поиск натуральных решений.

Как устроена работа

Пятнадцать заданий: выбор ответа, соответствие алгоритма и результата его работы, порядок шагов решета, вставка недостающих частей формулы Евклида и расчёты — НОД и НОК, число простых до 30, результат программ с алгоритмом Евклида и разложением на множители, число натуральных решений уравнения.

Разбор и подготовка

Повышенный уровень требует обоснований: почему в решете кратные вычёркивают начиная с квадрата, почему для проверки простоты хватает делителей до корня и когда линейное уравнение с двумя неизвестными не имеет целых решений вовсе.

Кому пригодится

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

Как проходит работа

Задания открываются в браузере на компьютере, планшете или мобильном телефоне, поэтому подойдёт любое устройство под рукой. Есть возможность настроить срок сдачи, что позволяет назначать комплект на дом. Система контроля добросовестности регистрирует переходы в посторонние вкладки и приложения во время выполнения.