Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của 2 số a,b

Yêu cầu:

– Nhập 2 số nguyên a,b.
a. Tìm USC lớn nhất của 2 số đó
b. Tìm bội số chung nhỏ nhất của 2 số đó

Phân tích:

– Dùng thuật toán Euclid để tìm USC lớn nhất

– BSC nhỏ nhất = a*b / USCLN(a, b)

Code:

/************************************************************
* Author: VNCODING
* History
* 2014/04/03 first create VNCODING
*************************************************************/
#include "stdio.h"
#include "conio.h"

int uscln(int a, int b);
int bscnn(int a, int b);
void main()
{
    int a = 6, b = 18;
    printf("USCLN(%d,%d) = %d\n", a, b, uscln(a, b));
    printf("BSCNN(%d,%d) = %d\n", a, b, bscnn(a, b));
    getch();
}
// dung thuat toan Euclid
int uscln(int a, int b)
{
    if(a == 0 && b == 0)
        return -1;
    else
        return (b == 0)? a : uscln(b, a%b);
}

int bscnn(int a, int b)
{
    if(a == 0 || b == 0)
        return -1;
    else
        return (a*b/uscln(a, b));
}

Kết quả:

USCLN(6,18) = 6
BSCNN(6,18) = 18

7 Comments on Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của 2 số a,b

  1. #include “stdafx.h”
    #include
    #include

    using namespace std;

    int ucln(int a, int b)
    {
    if (a == 0 || b == 0)
    return a + b;
    else
    if (a <= b)
    return ucln(a, b%a);
    else
    return ucln(b, a%b); //Có thể viết trong 1 dòng: return (a==0 || b==0) ? (a+b) : (a<=b) ? ucln(a, b%a) : ucln(b, a%b);
    }

    int main()
    {
    int num1, num2, temp;
    cout <> num1 >> num2;
    temp = ucln(abs(num1), abs(num2));
    if (temp == 0)
    cout << "Khong the tim UCLN(0,0)" << endl;
    else
    cout << "UCLN(" << num1 << "," << num2 << ") = " << temp << endl;
    return 1;
    }

Leave a Reply to VietVH Cancel reply