# Coprime numbers (Needs speed BOOST)

Hello,

I am new to ruby and am currently writing a program that takes the input ‘n’ and determines how many positive integers that are less than ‘n’ are relatively prime to ‘n’. I looked at Euclidean algorithm to determine the greatest common divisor for each of the numbers and than see if the GCD is 1, if it is 1 then the two numbers are relatively prime and I iterate a counter. However, n can be as large as 10^9 and with my current code if you type in n as 1000000000 it’ll take around a minute because of the repetitive calculations. There has to be a quicker way,there is a time limit of 1 second to compute this as well. It seems like making this program faster comes down to math theory. Any suggestions?

thanks

here is my code that works, just not fast enough

``````#!/usr/bin/ruby
def gcd(a, b)
a, b = b, a%b  until b.zero?
a
end

@rp = 0
n=0
while (1)
input = gets.chomp.to_i
if input == 0
break
end
for i in 1...input
gcd = gcd(input,i)

if gcd ==1
@rp += 1
end
end
puts"#{@rp}"

@rp=0
end
``````

Math:

Also, a few comments on the style of the Ruby code you’ve posted:

`while (1)`

Idiomatic version is `loop do`.

`input = gets.chomp.to_i`

`gets.to_i` is sufficient, because `to_i` ignores any non-numeric suffix.

``````if input == 0
break
end
``````

This shouldn’t be here, the code will not output anything if the input is zero.

`for in in 1...input`

Enumerable methods are preferred over `for` loops.

One way to refactor the block above is:

``````(1...input).each do |i|
@rp += 1 if gcd(input, i) == 1
end
``````

A more communicative way to write the above is:

``````@rp += (1...input).count { |i| gcd(input, i) == 1 }
``````

`puts"#{@rp}"`

String conversion is done by `puts`, so you can just:

``````puts @rb
``````

Lastly, there is no need for `@rp` to be an instance variable. Also it gets reset to 0 for each loop iteration, so it can live inside the `loop` (and `n` is unused).

A version of your code with all the suggested edits:

``````def gcd(a, b)
a, b = b, a % b until b.zero?
a
end

loop do
input = gets.to_i
puts (1...input).count { |i| gcd(input, i) == 1 }
end
``````

This should also be a few times faster than the original version. Still not enough to pass though, for that you need to change the algorithm (see the math link above for a hint).

2 Likes

Thank you for all the edits and advice! This was far beyond what I was looking for in an answer, I appreciate it!

I figured it out, thanks for the help! my run time went from >3seconds to .05s using the Euler Totient Function.

1 Like