Coprime numbers (Needs speed BOOST)

Ruby Questions
1

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
2

Math:

3

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
4

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

5

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

1 Like