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,

Co prime count — with Ruby

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 function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi, and may also be called Euler’s phi function.

In plain English, it is the number of integers k in the range 1 ≤ k ≤ n for 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 ~