Bài toán tìm ước số chung lớn nhất code

Đề bài: Viết chương trình tìm ước số chung lớn nhất [USCLN] và bội số chung nhỏ nhất [BSCNN] của 2 số nguyên dương a và b nhập từ bàn phím.

Định nghĩa

USCLN của 2 số nguyên dương a và b là một số k lớn nhất, sao cho a và b đều chia hết cho k.

BSCNN của 2 số nguyên dương a và b là một số h nhỏ nhất, sao cho h chia hết cho cả a và b.

Lời giải

Một phương pháp đơn giản đề tìm USCLN của a và b là duyệt từ số nhỏ hơn trong 2 số a và b cho đến 1, khi gặp số nào đó mà cả a và b đều chia hết cho nó thì đó chính là USCLN của a và b. Tuy vậy phương pháp này chưa phải là hiệu quả nhất.

Vào thế kỷ 3 TCN, nhà toán học Euclid [phiên âm tiếng Việt là Ơ-clit] đã phát minh ra một giải thuật tìm USCLN của hai số nguyên dương rất hiệu quả được gọi là giải thuật Euclid. Cụ thể về ý tưởng của bài toán, giả sử a lớn hơn b, khi đó việc tính UCSLN của a và b sẽ được đưa về bài toán tính USCLN của a mod b và b vì USCLN[a, b] = USCLN[a mod b, b].

Khi đã tìm được USCLN thì việc tìm BSCNN của hai số nguyên dương a và b khá đơn giản. Khi đó BSCNN[a, b] = [a * b] / UCSLN[a, b].

1. Tìm USCLN và BSCNN của 2 số nguyên dương trong Java bằng giải thuật Euclid

Ví dụ dưới đây sử dụng giải thuật Euclid để giải quyết bài toán tìm ước số chung lớn nhất [USCLN] và bội số chung nhỏ nhất [BSCNN] của hai số nguyên dương a và b.

File: BaiTap5.java

package vn.viettuts.baitap; import java.util.Scanner; /

• Chương trình tìm ước số chung lớn nhất [USCLN]
• và bội số cung nhỏ nhất [BSCNN] của 2 số a và b
• @author viettuts.vn / public class BaiTap5 {

  private static Scanner scanner = new Scanner[System.in];  
  /*  
  

  • main
  • @param args

     */  
    public static void main[String[] args] {  
        System.out.print["Nhập số nguyên dương a = "];  
        int a = scanner.nextInt[];  
        System.out.print["Nhập số nguyên dương b = "];  
        int b = scanner.nextInt[];  
        // tính USCLN của a và b  
        System.out.println["USCLN của " + a + " và " + b  
    

    • " là: " + USCLN[a, b]];

          // tính BSCNN của a và b  
          System.out.println["BSCNN của " + a + " và " + b  

    • " là: " + BSCNN[a, b]]; } /
  • Tìm ước số chung lớn nhất [USCLN]
  • @param a: số nguyên dương
  • @param b: số nguyên dương
  • @return USCLN của a và b / public static int USCLN[int a, int b] { if [b == 0] return a; return USCLN[b, a % b]; } /*
  • Tìm bội số chung nhỏ nhất [BSCNN]
  • @param a: số nguyên dương
  • @param b: số nguyên dương
  • @return BSCNN của a và b / public static int BSCNN[int a, int b] { return [a b] / USCLN[a, b]; } } Kết quả:

Nhập số nguyên dương a = 15 Nhập số nguyên dương b = 40 USCLN của 15 và 40 là: 5 BSCNN của 15 và 40 là: 120

2. Tìm USCLN và BSCNN của 2 số nguyên dương trong Java bằng cách khác

package vn.viettuts.baitap; import java.util.Scanner; /

• Chương trình tìm ước số chung lớn nhất [USCLN]
• và bội số cung nhỏ nhất [BSCNN] của 2 số a và b
• @author viettuts.vn / public class BaiTap5_2 {

  private static Scanner scanner = new Scanner[System.in];  
  /*  
  

  • main
  • @param args

     */  
    public static void main[String[] args] {  
        System.out.print["Nhập số nguyên dương a = "];  
        int a = scanner.nextInt[];  
        System.out.print["Nhập số nguyên dương b = "];  
        int b = scanner.nextInt[];  
        // tính USCLN của a và b  
        System.out.println["USCLN của " + a + " và " + b  
    

    • " là: " + USCLN[a, b]];

          // tính BSCNN của a và b  
          System.out.println["BSCNN của " + a + " và " + b  

    • " là: " + BSCNN[a, b]]; } /
  • Tìm ước số chung lớn nhất [USCLN]
  • @param a: số nguyên dương
  • @param b: số nguyên dương
  • @return USCLN của a và b / public static int USCLN[int a, int b] { int temp1 = a; int temp2 = b; while [temp1 != temp2] { if [temp1 > temp2] { temp1 -= temp2; } else { temp2 -= temp1; } } int uscln = temp1; return uscln; } /*
  • Tìm bội số chung nhỏ nhất [BSCNN]
  • @param a: số nguyên dương
  • @param b: số nguyên dương
  • @return BSCNN của a và b / public static int BSCNN[int a, int b] { return [a b] / USCLN[a, b]; } } Kết quả:

Nhập số nguyên dương a = 15 Nhập số nguyên dương b = 20 Ước số chung lớn nhất của 15 và 20 là: 5 Bội số chung nhỏ nhất của 15 và 20 là: 60 Giải thích hoạt động của chương trình trên: Trong chương trình này, tôi nhập vào hai số 15 và 20 thì trình biên dịch sẽ thực thi hàm uscln[] với các bước như sau: