C Ejemplo de práctica 16 - Máximo común divisor y mínimo común múltiplo

C 语言经典100例100 ejemplos clásicos del lenguaje C

Problema:Ingrese dos enteros positivos m y n, y encuentre su máximo común divisor y mínimo común múltiplo.

Análisis del programa:

(1) El mínimo común múltiplo = el producto de los dos números ingresados dividido por su máximo común divisor; la clave es encontrar el máximo común divisor;

(2) Para encontrar el máximo común divisor se utiliza el algoritmo de división repetida (también conocido como algoritmo de Euclides).

1) Demostración: Sea c el máximo común divisor de a y b, denotado como c=gcd(a,b), a>=b,
Sea r=a mod b
Supongamos a=kc, b=jc, entonces k y j son primos entre sí; de lo contrario, c no sería el máximo común divisor.
Según lo anterior, r=a-mb=kc-mjc=(k-mj)c
Se sabe que r también es múltiplo de c, y k-mj es primo relativo con j; de lo contrario, contradice el hecho de que k y j son primos entre sí,
Por lo tanto, el máximo común divisor de b y r también es c, es decir, gcd(a,b)=gcd(b,a mod b), queda demostrado.

2) Descripción del algoritmo:

Primer paso: a ÷ b, sea r el resto obtenido (0≤rSegundo paso: Intercambiar: asignar a←b, b←r, y volver al primer paso.

Ejemplo

// Created by www.example.com on 15/11/9. // Copyright © 2015 Tutorial para novatos. Todos los derechos reservados. // #include<stdio.h> int main() { int a,b,t,r,n; printf("Ingrese dos números:\n"); scanf("%d %d",&a,&b); if(a<b) {t=b;b=a;a=t;} r=a%b; n=a*b; while(r!=0) { a=b; b=r; r=a%b; } printf("El máximo común divisor de estos dos números es %d, y el mínimo común múltiplo es %d\n",b,n/b); return 0; }

El resultado de salida del ejemplo anterior es:

请输入两个数字:
12 26
这两个数的最大公约数是2,最小公倍数是156

C 语言经典100例100 ejemplos clásicos del lenguaje C

Otras extensiones