Máximo común divisor y mínimo común múltiplo en lenguaje C

El máximo común divisor y el mínimo común múltiplo en lenguaje C son los siguientes:

1 La idea común de la programación en lenguaje C del máximo común divisor es: seguir el mayor (el. menor de los dos enteros) Encuentra el primer número natural que pueda dividir dos enteros al mismo tiempo en orden desde el más pequeño (hasta el entero más pequeño 1), que es lo que quieres.

2. El máximo común divisor de dos números puede ser un decimal. Por lo tanto, al buscar el máximo común divisor en orden de mayor a menor, el valor inicial de la variable de bucle i comienza desde el decimal n. Decrecientemente, encuentre el primer número natural que pueda dividir dos números enteros al mismo tiempo y generelo.

3. Cabe señalar que aunque la condición de juicio es que i sea mayor que 0, no es necesario continuar el ciclo después de encontrar el primer valor de i que satisfaga la condición, como 25 y 15. , el máximo común divisor es 5. No es necesario ejecutar los siguientes 4, 3, 2 y 1, pero la condición de juicio aún está establecida en este momento y la única forma de finalizar el ciclo es con la interrupción. declaración.

El método para encontrar el mínimo común múltiplo en lenguaje C es el siguiente:

Los múltiplos comunes de dos o más números puente enteros se denominan múltiplos comunes, y el mínimo común múltiplo distinto de 0 se llama así El mínimo común múltiplo de varios números enteros. El mínimo común múltiplo de los enteros a y b se marca como a, b. De manera similar, el mínimo común múltiplo de a, b, c se marca como a, b, c. El mínimo común múltiplo de varios enteros también tiene la misma notación.

El concepto correspondiente al mínimo común múltiplo es el máximo común divisor. El máximo común divisor de a y b se registra como (a, b). Respecto al mínimo común múltiplo y al máximo común divisor, tenemos este teorema: a, b por a, b es igual a a por b (a, b son ambos números enteros).

Método exhaustivo

Supongamos que existen dos números enteros num1 y num2. El mínimo común múltiplo de estos dos enteros debe ser mayor o igual a su valor máximo, y al mismo tiempo menor. que o igual a su producto.

Recorre todos los números enteros en todo el rango en orden de pequeño a grande. El primer factor común es su mínimo común múltiplo. Independientemente de los números negativos, no tiene sentido encontrar el mínimo común múltiplo de un número negativo (equivalente a encontrar el máximo común múltiplo de dos números positivos)

Método del teorema

Usa el teorema para encontrar el mínimo común múltiplo (dos El mínimo común múltiplo de un número entero es igual al producto de dos números dividido por el máximo común divisor de los dos números Primero debes encontrar el máximo común divisor de los dos números enteros). El máximo común divisor aquí utiliza el método de división euclidiana.