Bài Tập Java Số 5: Tìm Ước Số Chung Lớn Nhất Của 2 Số Nguyên

Đề bài:

Cho 2 số nguyên a, b. Tìm ước số chung lớn nhất (USCLN) của chúng.
Input: a,b.
Output: USCLN của a và b.

Giải thuật:

USCLN của a và b là số nguyên dương lớn nhất mà cả a và b đều chia hết. Ta sử dụng bổ đề sau:
Giả sử a = bq + r với a,b,q,r là số nguyên , ta có:

Code mẫu:

package USCLN;

import java.util.Scanner;

public class USCLN {

 public static void main(String[] args) {
  int a, b;
  Scanner nhap = new Scanner (System.in);
  System.out.println("Nhap so thu nhat: ");
  a = nhap.nextInt();
  System.out.println("Nhap so thu hai: ");
  b = nhap.nextInt();
  if(a < 0)
   a = -a;
  if(b < 0)
   b = -b;
  if (a == 0 && b == 0)
   System.out.println("Khong co uoc so chung lon nhat");
  else 
  {
   while (a!= 0 && b!= 0)
   {
    if(a > b)
     a = a%b;
    else
     b = b%a;
   }
   if (a == 0)
    System.out.println(b); //b la USCLN.
   else
    System.out.println(a); //a la USCLN.
  }  
 } 
}