Ejemplos de ejercicios C 16-- máximo común divisor y el mínimo común múltiplo

100 casos de lengua clásica C

Título: Introduzca dos enteros positivos m y n, buscando el máximo común divisor y el mínimo común múltiplo.

Programa de análisis:

(1) Producto = mínimo común múltiplo de dos números introducidos, además de su denominador común, la clave está en encontrar el denominador común;

(2) máximo común divisor utilizando el algoritmo euclidiano (también conocido como algoritmo de Euclides)

1) Demostración: Sea c es el máximo común divisor de a y b, denotado por c = mcd (a, b), a> = b,
Por lo tanto r = a mod b
Deje a = kc, b = x, entonces k, j son primos entre sí, de otro modo c no es el máximo común divisor
De acuerdo con el, r = a-mb = kc-MJC = (k-mj) c
Rc es visto múltiplos, y k-mj y j son primos entre sí, de lo contrario el mencionado k, j primos entre sí contradicción,
Se puede observar, b y r es el máximo común divisor c, es decir, mcd (a, b) = mcd (b, a mod b), demostró.

2) descripción del algoritmo:

El primer paso: a ÷ b, de modo que R es un resto (0≤r Paso dos: Intercambio: establecer un ← b, b ← r, y devuelve el primer paso.

Código fuente:

//  Created by www.w3big.com on 15/11/9.
//  Copyright © 2015年 本教程. All rights reserved.
//

#include<stdio.h>
int main()
{
    int a,b,t,r;
    printf("请输入两个数字：\n");
    scanf("%d %d",&a,&b);
    if(a<b)
    {t=b;b=a;a=t;}
    r=a%b;
    int n=a*b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    printf("这两个数的最大公约数是%d，最小公倍数是%d\n",b,n/b);
    
    return 0;
}

La salida del ejemplo anterior es:

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

100 casos de lengua clásica C