# Co prime count — the optimized version

Hello my very-limited audience, hope you’ve all been splendid! So this post is the continuation of the problem we started with,

We finished the brute-force approach, time to implement the super-fast version of it, or how we like to call it, a solution that works well even in like when the input size is humongous, and we want to give the best result such that the time taken and space utilized is still minimal :D

Here we go;

`require "prime"class CoPrime  def count_coprime(input)    array = []    input.each do |num|      array << num.prime_division.inject(1) { |result, (prime, exp)|                result *= (prime-1) * prime**(exp-1) }    end    print "The count of co prime counts are #{array}\n"  endend`

Phew. Lots of new stuff up there. Let’s start with the logic here. So this very amazing person, Euler, gave us this beautiful and direct approach, Euler’s totient , a formula to determine the co-prime count for any number!

I need you to go through this — an example demonstrating the Euler’s formula

Coming back to earth, and putting the Ruby hat back on, as you can see in the code snippet, I have required the ‘Prime’ class, to make use of the prime_division method.

For the input=[5,8,14], let’s break down the code line —

`input.each do |num|  array << num.prime_division.inject(1) { |result, (prime, exp)|            result *= (prime-1) * prime**(exp-1) }end`

it looks something like this;

I hope the above explanation made things clear for you. If not, please hit me up in the comments, I’d be happy to help ( after I go through this another 5 times in the hopes of engraving it :smh: )

Also, if there’s another variation of it that you have in mind, please do share! I’d love to learn.

Until next time, toodles ~

--

--

## More from Niyanta Zamindar

I read. I evolve. I get out of hibernation. I write.

## Get the Medium app

I read. I evolve. I get out of hibernation. I write.