"Информатика (базовый и углублённый уровни) (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Целочисленные алгоритмы решают задачи, связанные с делимостью, поиском наибольшего общего делителя и простых чисел. Их основа — деление с остатком: оно помогает проверить, делится ли число на другое, и шаг за шагом найти НОД. Чтобы проверить число на простоту, достаточно перебирать делители до его квадратного корня, а для поиска всех простых чисел до заданной границы применяют решето Эратосфена. Эти идеи важны и для программирования, и для математики.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Целочисленное деление с остатком — для целых a и b, где b ≠ 0, это определение частного q и остатка r так, чтобы a = bq + r и 0 ≤ r < |b|. Например, при 17 : 5 получаем q = 3 и r = 2. Такое представление помогает узнавать, делится ли одно число на другое, и служит основой алгоритма Евклида.
Наибольший общий делитель (НОД) — наибольшее натуральное число, на которое без остатка делятся оба заданных целых числа. Например, общие делители 12 и 18 — 1, 2, 3 и 6, поэтому НОД равен 6. НОД нужен, в частности, чтобы сокращать дроби и отношения.
Алгоритм Евклида — способ нахождения НОД последовательной заменой пары чисел на делитель и остаток от деления. Например, пару 18 и 12 заменяют на 12 и 6, затем на 6 и 0. Последний ненулевой остаток даёт НОД, поэтому алгоритм позволяет обойтись без перебора всех делителей.
Простое число — натуральное число больше 1, имеющее ровно два натуральных делителя: 1 и само число. Например, у 7 делители только 1 и 7, а у 8 есть ещё 2 и 4. Различение простых и составных чисел помогает решать задачи о делимости и разложении чисел на множители.
Остаток от деления показывает, какая часть числа не вместилась в целое число групп размера b. Если a mod b = 0, остатка нет, значит a делится на b без остатка; если остаток ненулевой, делимость не выполняется. В программе целочисленное деление получает частное без дробной части, а операция mod — остаток. Вместе они позволяют проверять делимость и выполнять шаги других целочисленных алгоритмов.
Алгоритм Евклида работает благодаря тому, что общий делитель чисел a и b одновременно делит и остаток от деления a на b: остаток равен a − bq. Поэтому НОД(a, b) совпадает с НОД(b, a mod b), и замену пары можно повторять, не меняя ответа. Остатки при делении на положительные числа уменьшаются, так что последовательность не может продолжаться бесконечно. Когда остаток равен нулю, последний ненулевой остаток и есть НОД.
При проверке n на простоту не требуется делить его на все числа до n. Если n составное, его можно представить как произведение двух натуральных множителей, и хотя бы один из них не превосходит √n: иначе произведение было бы больше n. Поэтому, если целых делителей от 2 до √n не нашлось, число простое. Проверку начинают с числа 2, а числа меньше 2 сразу относят к непростым.
Границу цикла при проверке простоты удобно задавать условием d · d ≤ n: оно эквивалентно d ≤ √n и позволяет не вычислять корень. Если цикл дошёл до конца и ни один остаток n mod d не равен нулю, делителя не существует. После √n проверка избыточна: возможные делители уже образуют пары, и для каждой пары меньший множитель был бы проверен. Граничное условие важно, чтобы не пропустить делитель, равный √n, например 3 у числа 9.
Решето Эратосфена находит сразу все простые числа до заданного n. Сначала числа от 2 до n считают возможными простыми, затем берут очередное неотмеченное число p и отмечают его кратные как составные. Начинать отметку можно с p²: кратные p, меньшие p², уже имеют меньший простой делитель и были отмечены раньше. Достаточно обрабатывать p, пока p² ≤ n; если после этого остались неотмеченные числа, они простые.
| Алгоритм | Что решает | Основная идея | Когда завершает работу |
|---|---|---|---|
| Деление с остатком | Находит частное и остаток | Представляет a как bq + r | После вычисления q и r |
| Алгоритм Евклида | Находит НОД двух чисел | Заменяет пару на делитель и остаток | Когда остаток равен нулю |
| Проверка числа на простоту перебором делителей | Определяет, простое ли n | Проверяет делители от 2 до √n | При найденном делителе или после проверки всей границы |
| Решето Эратосфена | Находит все простые числа не больше n | Отмечает кратные очередных неотмеченных чисел | После обработки чисел p, для которых p² ≤ n |
Чтобы выбрать алгоритм, сначала определите, что требуется получить: остаток, НОД, ответ о простоте одного числа или список простых чисел. Затем смотрите на условие остановки: оно помогает правильно построить цикл и не выполнять лишние шаги. В таблице указаны именно эти различия.
Задача. Для заданных целых a и b определить, делится ли a на b без остатка. По условию нельзя просто вычислить остаток, не проверив делитель: операция деления на ноль не определена. Если b ненулевое, достаточно проверить одно значение — a mod b.
Ответ. Для ненулевого b число a делится на b тогда и только тогда, когда a mod b = 0. Для b = 0 нужно отдельно сообщить о невозможности деления.
Задача. Найти НОД чисел 252 и 105. Перебирать делители обоих чисел не нужно: алгоритм Евклида позволяет заменять числа на меньшую пару с тем же НОД. На каждом шаге делим большее число на меньшее и оставляем остаток.
Ответ. НОД(252, 105) = 21. Проверка: 252 = 21 · 12, а 105 = 21 · 5, то есть 21 делит оба числа.
Задача. Вывести все простые числа от 2 до заданного n. Если проверять каждое число отдельным циклом, придётся повторять проверки делителей; решето использует общую информацию о кратных. Для примера возьмём n = 20 и заведём отметки: отмеченное число составное, а неотмеченное после работы решета простое.
Ответ. При n = 20 простые числа от 2 до n — 2, 3, 5, 7, 11, 13, 17, 19. Для другого n порядок действий тот же, меняется только верхняя граница.
Считать простыми 0 и 1. Эти числа не удовлетворяют определению простого числа: простые должны быть больше 1 и иметь ровно два натуральных делителя. Ошибку допускают, если ограничиться проверкой «не нашлось делителей». Перед перебором проверьте, что n ≥ 2; для меньших значений сразу выдавайте ответ «не простое».
Перебирать делители до n. Такой цикл делает лишнюю работу и повышает риск ошибиться в его границе, например выйти за пределы допустимых значений. Для составного n достаточно найти делитель не больше √n. Проверьте условие цикла на квадрате: для n = 49 делитель 7 должен попасть в проверку, поэтому подходит условие d · d ≤ n.
Продолжать алгоритм Евклида после нулевого остатка или принять ноль за ответ. Нулевой остаток означает, что предыдущий делитель делит числа без остатка, поэтому следующий шаг уже не нужен. Путаница возникает, если считать текущий остаток ответом, не сохранив предыдущий. Проверьте последнюю пару: при делении на последнем шаге остаток равен нулю, а НОД — делитель этого шага, то есть последний ненулевой остаток.
Начинать вычёркивание кратных p с 2p. Это не делает результат неверным, но кратные, уже отмеченные при обработке меньших простых чисел, приходится обрабатывать повторно. Для каждого p можно начать с p², потому что его меньшие кратные имеют меньший простой делитель. Проверьте на p = 5: числа 10, 15 и 20 уже будут отмечены при обработке 2 или 3.
Для целочисленных алгоритмов нужны целочисленное деление, остаток, условия и циклы: с их помощью записывают шаги и задают момент остановки. НОД используют при сокращении дробей и отношений, а проверки делимости помогают решать задачи о разбиении на равные группы. Простые числа и разложение на множители встречаются в комбинаторике и теории чисел. Эти же понятия применяются в криптографии, где свойства чисел участвуют в построении методов защиты данных.
Почему для проверки числа на простоту достаточно перебирать делители до квадратного корня?
Если n = a · b и оба множителя больше √n, их произведение было бы больше n. Значит, у составного числа обязательно найдётся делитель не больше √n, и проверять более крупные числа не нужно.
Что именно нужно повторять в алгоритме Евклида?
Нужно делить первое число на второе и заменять пару чисел на делитель и остаток: (a, b) становится (b, a mod b). Шаги повторяют, пока остаток не станет нулём.
Как узнать, делится ли одно число на другое без остатка?
Нужно вычислить остаток от деления первого числа на второе. Если остаток равен нулю, деление выполняется без остатка; делитель не должен быть равен нулю.
Почему 1 не считается простым числом?
Простое число должно иметь ровно два натуральных делителя: 1 и само число. У числа 1 только один натуральный делитель — оно само.
С какого числа начинать вычёркивать кратные в решете Эратосфена?
Для очередного простого числа p можно начинать с p². Меньшие кратные p уже были отмечены при обработке простых делителей, поэтому повторно вычёркивать их незачем.
§ 38. Целочисленные алгоритмы
