最快速的方法來檢查一個向量是否包含至少一個coprime對在MATLAB中

Question

我想在MATLAB中編寫一個函數來確定一個數組是否至少包含一個coprime對。從形式上看，兩個整數n和m是互質數，如果gcd(m,n)==1.

，我要建立一個輸入向量x，並返回一個true/false值的功能。如果x包含兩個不同的元素n,m，則該值將爲真，如gcd(n,m)==1.否則應返回false。因此，我們需要它表現爲：

x = [1,2,3,4]; 
iscoprime(x) 
> true 

和

x = 2*[1,2,3,4]; 
iscoprime(x) 
> false 

我現在在這個最好的嘗試是下面的函數。

function value = has_coprime_pair(x) 

%take out zeros 
x(x==0) = []; 

%take absolute value 
x = abs(x); 

%make sure we have elements 
if isempty(x) 

    value = true; 

%make sure all elements are integers 
elseif any(x~=floor(x)) 

    value = false; 

%check if any element = 1 
elseif any(x==1) 

    value = true; 

%check if any pair of elements is coprime 
else 

    %get prime factors of all elements 
    prime_factors = arrayfun(@(x) factor(x), x, 'UniformOutput', false); 
    all_factors  = unique(cell2mat(prime_factors)); 

    %remove 1 from the list of all prime factors 
    all_factors(all_factors==1) = []; 

    %x does not contain coprime pair if each element has the same prime factor 
    value = true; 

    for f = all_factors 

     can_be_factored_by_f = cellfun(@(p) any(f==p),prime_factors,'UniformOutput',true); 

     if all(can_be_factored_by_f) 
      value = false; 
      break 
     end 

    end 

end 


end 

任何人都可以建議一個更快的方法嗎？

Answer 1

如果你擔心正確性，你應該知道你的現有代碼失敗：

>> has_coprime_pair([6 10 15]) 

ans = 

    1 

如果速度比正確更重要的是，你可以只使用

function value = has_coprime_pair(x) 
    value = true; 
end 

要直接實現您的定義：

value = any(any(1 == bsxfun(@gcd, x, x'))) 

不知道的速度，但它憑藉的是正確的：

EDU>> has_coprime_pair([6 10 15]) 

ans = 

    0 

EDU>> has_coprime_pair([1 2 3 4]) 

ans = 

    1 

EDU>> has_coprime_pair(2*[1 2 3 4]) 

ans = 

    0 

Answer 2

我不知道這是更快，但它絕對簡單：

function result = has_coprime_pair(x) 

for ii = 2:numel(x) 
    result = false; 
    if any(gcd(x(ii),x(1:ii-1)) > 1) %// test each pair of nunmbers only once 
    result = true; 
    break 
    end 
end