Javascript - Tìm ước số chung của 2 số
Tìm ước số chung của 2 số
Viết một hàm JavaScript để nhận ước chung lớn nhất (gcd) của hai số nguyên.
Theo Wikipedia - Trong toán học, ước số chung lớn nhất (ƯSCLN) hay ước chung lớn nhất (ƯCLN) của hai hay nhiều số nguyên là số nguyên dương lớn nhất là ước số chung của các số đó. Ví dụ, ước chung lớn nhất của 6 và 15 là 3 vì {\displaystyle 6:3=2}
Trong tiếng Anh, ước chung lớn nhất gọi là greatest common divisor (gcd), greatest common factor (gcf),[1] highest common factor (hcf),[2] greatest common measure (gcm),[3] hay highest common divisor.[4]
Trong trường hợp tất cả số nguyên đều bằng 0 thì chúng không có ƯCLN vì khi đó mọi số tự nhiên khác không đều là ước chung của các số đó. Nếu trong các số đó có ít nhất một số bằng 0 và ít nhất một số khác 0 thì ƯCLN của chúng bằng ƯCLN của các số khác 0.
Ví dụ:
Mã nguồn:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>GCD (greatest common divisor) of more than 2 integers</title>
<script>
function gcd_more_than_two_numbers(input) {
if (toString.call(input) !== "[object Array]")
return false;
var len, a, b;
len = input.length;
if ( !len ) {
return null;
}
a = input[ 0 ];
for ( var i = 1; i < len; i++ ) {
b = input[ i ];
a = gcd_two_numbers( a, b );
}
return a;
}
function gcd_two_numbers(x, y) {
if ((typeof x !== 'number') || (typeof y !== 'number'))
return false;
x = Math.abs(x);
y = Math.abs(y);
while(y) {
var t = y;
y = x % y;
x = t;
}
return x;
}
document.write(gcd_more_than_two_numbers([3,15,27])+"<br/>");
document.write(gcd_more_than_two_numbers([5,10,15,25])+"<br/>");
</script>
</head>
<body>
</body>
</html>
Lưu đồ thuật toán:
