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"
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!

monkey see. monkey do

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;

how-it-works

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 ~

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store