ГДЗ по информатике 8 класс Босова, номер §3.2 № 3

§. № Алгоритм нахождения НОК

Приведите словесное описание алгоритма нахождения наименьшего общего кратного (НОК) двух целых чисел: а) с помощью разложения чисел на простые множители; б) через НОД.

Решение

Для нахождения НОК положительных целых чисел применим два способа. НОК — наименьшее положительное число, которое делится на оба данных числа.

а) Разложение на простые множители. Сначала делим каждое число на простые числа, пока в частном не получим . Затем выписываем каждый простой множитель столько раз, сколько он встречается в том из двух разложений, где его повторений больше. Перемножаем выписанные множители. В произведении есть все множители, необходимые для делимости на каждое из исходных чисел, а лишних множителей нет.

Например, , . Берём две двойки и две тройки: . Число делится и на , и на .

б) Через НОД. Находим наибольший общий делитель двух чисел. Затем произведение данных чисел делим на этот НОД: . Общие простые множители входят в произведение дважды; деление на НОД убирает лишнее повторение.

Для тех же чисел , поэтому . Оба алгоритма дают одинаковый результат.

Ответ

а) Разложить числа на простые множители, взять каждый множитель с наибольшей встречающейся кратностью и перемножить. б) Найти НОД и вычислить .

Помогло?

Номер §3.2 № 3