algorithm - 如何使用 MATLAB 快速检查数组是否互质

Question

我想在 MATLAB 中编写一个函数，可以快速判断一个数组是否互质。形式上，我们说一个 N x 1 数组 x 是互质的，如果整除所有 N 个元素的最大正整数是 1(请参阅此处了解更广泛的 definition)。

我想到的函数应该输入一个整数数组 x，如果 x 是互质的，则输出 true。一些例子:

%example
x = [6,10,15];
iscoprime(x)
> true

%counter-example
x = 2*[1,2,3];
iscoprime(x)
> false

---

回答 目前最好的尝试是:

function value = iscoprime(x)

%remove 0 and take absolute value
x = abs(x(x==0));
nx = length(x);

%return true if all original entries = 0
if nx == 0, value = true;

%return false if x only contains 1 value and it is not 1
elseif nx == 1 & x~=1, value = false;

%return true if x contains a 1 (easy way to tell if x is coprime)
elseif any(x==1), value = true;

%check if x is coprime (based on Yasen's answer)
else

    v = x(1);
    for i = 2:nx
        v = gcd(v,x(i));
        if (v == 1), 
            value = true;
            break
        end
    end
    value = false;

end
end

谁能推荐一个更快的方法？

Answer 1

您可以使用 the built in MATLAB function用于为数组中的每两个连续数字找到最大公约数 (GCD)，并将结果累加到某个变量 GCD 中。如果 GCD = 1，则数字互质。否则，它们不是互质的，并且 GCD 是它们的公因数。

代码如下:

function GCD = iscoprime(x) % assuming x is an array, 
    GCD = x(1);             % returning greatest common divisor for the array
    for i=1:size(x, 2)
        GCD = gcd(GCD, x(i));
    end
end