# 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 *worst-cases, *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"

end

end

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!

In number theory,

Euler’s totient functioncounts the positive integers up to a given integernthat are relatively prime ton. It is written using the Greek letter phi, and may also be calledEuler’s phi function.

In plain English, it is the number of integers

kin the range 1 ≤k≤nfor which the greatest common divisor gcd(n,k) is equal to 1.

**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 ~