CODEWITHSUNDEEP
matlabprimesprime-factoring
Berk U.
Berk U.

Reputation: 7188

Quickest way to check if a vector contains at least 1 coprime pair in MATLAB

I would like to write a function in MATLAB to determine whether an array contains at least one coprime pair. Formally, two integers n and m are co-prime if gcd(m,n)==1.

The function that I am building should input a vector x, and return a true/false value. This value will be true if x contains two distinct elements n,m such that gcd(n,m)==1. It should return false otherwise. Thus, we need it to behave as:

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

and 

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

My current best attempt at this is the following function.

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

Can anyone suggest a faster method?

Upvotes: 1

Views: 637

Answers (2)

Luis Mendo
Luis Mendo

Reputation: 112749

I don't know if this is faster, but it's definitely simpler:

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

Upvotes: 2

Ben Voigt
Ben Voigt

Reputation: 283733

If you're worried about correctness, you should know that your existing code fails for:

>> has_coprime_pair([6 10 15])

ans =

     1

If speed is more important than correctness, you could just use

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

To directly implement your definition:

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

Not sure about the speed, but it has the virtue of being correct:

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

Upvotes: 2

Related Questions