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
```