НОК и НОД. Алгоритм Евклида

Предлагается использовать следующие определения:

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

Наибольшим общим делителем (НОД) двух натуральных чисел x  и y  называется такое натуральное число, на которое делятся эти числа и частные от этого деления взаимно просты.

Задача нахождения НОД возникает при сокращении числовых дробей, задача нахождения НОК – при приведении их к общему знаменателю.

Сначала рассмотрим нахождение НОК и НОД путем разложение двух натуральных чисел x  и y  на простые множители.

Рациональный способ поиска простых делителей для больших чисел.

Сначала проверяем делимость на наименьшие простые числа 2, 3, 5, 11, поскольку во - первых, чем меньше делитель, тем среди всех чисел больше чисел, делящихся на него, а во - вторых, на эти делители есть признаки делимости. Затем проверяем делимость на 7, 13, …

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

Весь материал - смотрите документ.