Problem
Có một phiên bản khác của thuật toán Euclid, trong đó thao tác trừ được thay thế bằng thao tác tính phần dư.
Phiên bản này được coi là thích hợp hơn hiện nay, vì tính trung bình, nó chứa số bước nhỏ hơn đáng kể. Tuy nhiên, vào thời mà máy tính lớn và chậm, bản thân phép chia có thể là một quy trình phức tạp. Và sau đó, phiên bản đầu tiên của thuật toán có thể hiệu quả hơn.
Thực hiện thuật toán Euclid bằng cách thay thế phép trừ bằng phép toán modulo.
Cho hai số tự nhiên
A và
B. Viết hàm
nod(A, B) trả về ước chung lớn nhất của
A và
B.
Ví dụ về chương trình
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
12 42 |
6 |
Hãy nhớ rằng bạn không thể sử dụng vòng lặp trong giải pháp của mình.
Bạn chỉ cần viết hàm, không cần nhập xuất gì cả!
Запрещенные операторы: for;while;do;until;gcd