3

The exercise I'm working on asks "Write a method, coprime?(num_1, num_2), that accepts two numbers as args. The method should return true if the only common divisor between the two numbers is 1."

I've written a method to complete the task, first by finding all the factors then sorting them and looking for duplicates. But I'm looking for suggestions on areas I should consider to optimize it.

The code works, but it is just not clean.

def factors(num)
 return (1..num).select { |n| num % n == 0}
end

def coprime?(num_1, num_2)
  num_1_factors = factors(num_1)
  num_2_factors = factors(num_2)
  all_factors = num_1_factors + num_2_factors
  new = all_factors.sort
  dups = 0
  new.each_index do |i|
    dups += 1 if new[i] == new[i+1]
  end
  if dups > 1
    false
  else
    true
  end    
end

p coprime?(25, 12)    # => true
p coprime?(7, 11)     # => true
p coprime?(30, 9)     # => false
p coprime?(6, 24)     # => false
Joe Horn
  • 49
  • 3
  • 1
    Maybe https://en.wikipedia.org/wiki/Euclidean_algorithm ? – ymonad May 29 '19 at 02:13
  • I can use anything at this point. I'm in a beginning ruby class, but they are no limitations so I will check this out. If we can come up with a better way to do something then more power to us. The instructor even told us stack overflow would be our friend. – Joe Horn May 29 '19 at 03:58
  • I hadn't noticed @panic's answer earlier. I therefore deleted my earlier comment and will delete this one as well. You may wish to delete your reply to my earlier comment. – Cary Swoveland May 29 '19 at 05:00

3 Answers3

2

You could use Euclid's algorithm to find the GCD, then check whether it's 1.

def gcd a, b
  while a % b != 0
    a, b = b, a % b
  end
  return b
end

def coprime? a, b
  gcd(a, b) == 1
end

p coprime?(25, 12)    # => true
p coprime?(7, 11)     # => true
p coprime?(30, 9)     # => false
p coprime?(6, 24)     # => false```
GBrandt
  • 685
  • 4
  • 11
1

You can just use Integer#gcd:

def coprime?(num_1, num_2)
  num_1.gcd(num_2) == 1
end
Panic
  • 2,229
  • 23
  • 25
0

You don't need to compare all the factors, just the prime ones. Ruby does come with a Prime class

require 'prime'

def prime_numbers(num_1, num_2)
  Prime.each([num_1, num_2].max / 2).map(&:itself)
end

def factors(num, prime_numbers)
  prime_numbers.select {|n| num % n == 0}
end

def coprime?(num_1, num_2)
 prime_numbers = prime_numbers(num_1, num_2)
 # & returns the intersection of 2 arrays (https://stackoverflow.com/a/5678143)
 (factors(num_1, prime_numbers) & factors(num_2, prime_numbers)).length == 0
end
AbM
  • 7,326
  • 2
  • 25
  • 28