Паскаль. Основы программирования


Задание 4


Составьте программу определения наименьшего общего кратного (НОК) двух чисел по меньшей мере двумя способами.


Напоминание

Наименьшим общим кратным двух чисел a и b, НОК(a, b) называется наименьшее число, которое делится и на a и на b.

Например, для чисел 18 и 27 наименьшим общим кратным является число 54. Оно делится без остатка и на 18 и на 27. Хотя  общих кратных

для этих чисел существует бесконечно много: 54, 108, 162, 216, ..., однако, 54 является меньшим среди них.

Подсказка

1. Идея составления первой программы или, иначе говоря, идея первого алгоритма состоит в следующем.

Выбираем большее из чисел, если оно делится на меньшее, тогда оно и будет являться наименьшим общим кратным, иначе, большее число увеличивается вдвое, т.е. к нему прибавляется само это число и снова происходит проверка, делится ли новое число на меньшее, если делится, тогда оно является НОК, если не делится, тогда снова увеличивается на такое же число, т.е. первоначальное большее из двух уже увеличивается втрое и так далее.

Например, для чисел 10 и 36 этот процесс будет выглядеть так: 36 большее из чисел, 36 mod 10 <>0, т.е. 36 не делится на 10; увеличим 36 на 36, получим:

 проверяем: 72 mod

10 <> 0; увеличим 72 еще на 36, получим:

 проверяем: 108 mod 10 <> 0; увеличиваем на 36, получим:
 проверяем: 144 mod 10 <> 0; увеличиваем:
 проверяем: 180 mod 10=0, 180 делится на 10, значит 180 и является наименьшим общим кратным чисел 10 и 36, НОК(10, 36) = 180.

2. Идея второго алгоритма основывается на следующем математическом утверждении: a

b = НОК(a, b)
НОД(a, b).

Пример 3. Составить программу, которая определяет является ли данное число n простым.

Простым называется натуральное число, которое имеет только два делителя - 1 и само себя. Надо заметить, что число 1 не подходит под это определение, так как имеет только один делитель - само себя, а значит не является простым числом.

Натуральные числа, отличные от 1 и не являющиеся простыми называются составными.




Начало  Назад  Вперед