<!DOCTYPE html>
<html>
<head lang="en">
<meta charset="UTF-8">
<title></title>
<script type="text/javascript" src="jquery.min.js"></script>
<script type="text/javascript">
//判断是否为质数------------------------------------------------------
function isPrime(n) {
for (var i = n - 1; i > 1; i--) {
if (n % i == 0) {
return false;
}
}
return true;
}
// ---------------------------------------------------
//求出一个数(非质数)的质因数--------------------------------------------------------
function primeArray(n, array) {
array = new Array();
for (var i = 2; i < n; i++) {
//是否为质数
if (isPrime(i)) {
var temp_R = n % i;//余数
var temp_c = n / i;//商
//是否整除
if (temp_R == 0) {
array.push(i);
if (!isPrime(temp_c)) {
//商不为质数
array = array.concat(primeArray(temp_c, array));
} else {
array.push(temp_c);
}
break;
}
}
}
return array;
}
// 查找两个数组的相同部分-----------------------------------
function findSamePart(a, b) {
var temp = new Array();
for (var i = 0; i < a.length; i++) {
for (var j = 0; j < b.length; j++) {
if (a[i] == b[j]) {
temp.push(a[i]);
a.splice(i, 1);
b.splice(i, 1);
i =0;
continue;
}
}
}
return temp;
}
//---------------------------------------------------
// 分解质因数求最大公因数-----------------
function gcd(a, b) {
if (isPrime(a) || isPrime(b)) {
return 1;
}
var a = parseInt($("#a").val());
var b = parseInt($("#b").val());
var a_array = new Array();
var b_array = new Array();
var a_array = primeArray(a, a_array);
var b_array = primeArray(b, b_array);
var temp = findSamePart(a_array, b_array);
var sum = 1;
for (var i = 0; i < temp.length; i++) {
sum = sum * temp[i];
}
return sum;
}
</script>
</head>
<body>
<div>
<h1>分解质因数法</h1>
<input type="number" id="a" placeholder="整数a"></br>
<input type="number" id="b" placeholder="整数b">
</br>
<input type="button" value="求最大公约数" onclick="demo();">
<script type="text/javascript">
function demo() {
var a = $("#a").val();
var b = $("#b").val();
alert(a+"和"+b+"的最大公约数是"+gcd(a, b));
}
</script>
</div>
</body>
</html>