Co prime count — with Ruby

Centering this post around an interesting problem I came across. Made me brush up a lot of concepts :)

Premise: What are co-primes? Co-primes are numbers that share 1 as their greatest common divisors.

Problem statement: Given an array of positive integers, return another array which will be the count of all co-prime between those elements. Let’s break it down with an example.
input = [5,8,14] ; output = []
input[0] = 5, which is a prime number. All numbers greater than 0, 1–4 are co-prime to 5, because they all share 1 as the GCD. So, output[0] = 4 ; which is the count of co-primes.
Similarly, input[1] = 8, the integers [2,4,6] share at least the common divisor of of 2 with 8. The 4 values, [1,3,5,7] are co-primes, so output[1] = 4.
And lastly, input[2] = 14, the integers [2,4,6,7,8,10,12] share a common divisor > 1 with 14. The 6 co-primes are [1,3,5,9,11,13], so output[2] = 6.

So my output array looks like, [4,4,6].

Photo by James Harrison on Unsplash

Did that give you a headache? Surely gave me one the first time I was trying to wrap my head around it.

Let’s try to solve this problem. There are 2 main approach to solve any problem, the Brute-force approach and the optimized approach. Most of us start off with the brute-force method, seems very obvious, is easier to implement. Here goes nothing!

Solution:
Taking advantage of the vast in-built library that Ruby provides, we are going to utilize the “gcd” function from the Integer class. As the name suggests, gcd function returns the greatest common divisor of the two integers. The result is always positive.

def count_coprime(input)
  coprime_count_array = []
  input.each do |i|
    coprime_count_array << (1…i).count { |a| i.gcd(a) == 1 }
  end
end

Viola! There goes my “will work if the input size is always small, but will cause havoc once the size is too big!!”. Why you ask? Because for every element (i), I start calculating from 1.
So in case my input array decides to be -

[12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187]

we’ll have to stay around to help clean up after the party!! We have massive time complexity issues *tsk tsk*, but hey, at least it works :D

In the interest of keeping the post short ish, I will go over the optimized approach in the next post. Stay tuned!

Part 2 is up — optimized solution :))