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


Задание 3


Составьте программу, которая будет находить число делителей и их сумму для данного натурального числа.

Пример 2. Найти наибольший общий делитель (НОД) двух чисел a и b.

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

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

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

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

Прежде четко определим для себя, что такое НОД двух чисел. Так, для чисел 36 и 45 существуют три общих делителя: 1, 3, 9. Наибольший среди них 9. Он и является НОД чисел 36 и 45.

Для 30 и 45 немного больше общих делителей: 1, 3, 5 и 15. Наибольшим является 15, значит НОД(30, 45) = 15.

Наибольшим общим делителем чисел a и b называется наибольшее число среди всех общих делителей чисел a и b.

Тогда, по логике вещей, возникает естественная идея найти НОД следующим образом.

Во-первых, надо проверить не делится ли одно из чисел на другое, если

делится, тогда то на которое разделилось и является наибольшим общим делителем. Например, для чисел 45 и 15 НОД будет число 15. Если

ни одно из них не делится на другое, тогда будем брать поочередно все натуральные числа от 1 до меньшего из чисел a или b и проверять на какие из них делятся оба числа, последний из этих общих делителей и будет наибольшим.

Такой процесс для чисел 36 и 45 будет выглядеть так:

проверяем деление a на b и b на a;

находим остаток от деления на 1, 36 mod 1= 0, 45 mod 1 = 0, значит 1 - общий делитель;

на 2, 36 mod

2 = 0, 45 mod 2 <>0, 2 не является общим делителем;

на 3, 36 mod

3 = 0, 45 mod 3 = 0, 3 - общий делитель;




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