Ước chung lớn nhất từ các thừa số nguyên tố

Liệt kê các ước số sẽ chậm khi số lớn hơn, còn phân tích thành thừa số nguyên tố thì nhanh hơn. Phân tích cả hai số: 45 bằng $3\cdot 3\cdot 5$ và 75 bằng $3\cdot 5\cdot 5$. Các số nguyên tố chung là một số 3 và một số 5.

Nhân các số nguyên tố chung: $3\cdot 5$ bằng 15, là ước chung lớn nhất của 45 và 75. Một số nguyên tố chỉ được tính là số chung với số lần xuất hiện trong cả hai số: 45 có hai số 3 nhưng 75 chỉ có một, nên chỉ tính một số 3.

Vì sao cách này hiệu quả: ước chung chỉ có thể được tạo từ các số nguyên tố có trong cả hai số. Lấy mỗi số nguyên tố chung nhiều lần nhất có thể ở cả hai số sẽ tạo ra ước chung lớn nhất. Với số mũ, lấy mỗi số nguyên tố chung với số mũ nhỏ hơn: ${3}^{2}\cdot 5$ và $3\cdot {5}^{2}$ cho ra $3\cdot 5$.