Skip to content

Instantly share code, notes, and snippets.

@jetpks
Created June 20, 2012 05:20
Show Gist options
  • Select an option

  • Save jetpks/2958260 to your computer and use it in GitHub Desktop.

Select an option

Save jetpks/2958260 to your computer and use it in GitHub Desktop.
Find the a number coprime to the input
#!/usr/bin/env ruby
## Initialization and parameter checking:
def usage
puts "Usage: ./coprime.rb integer\n"
Process.exit(1)
end
if ARGV.length != 1
puts "Error: wrong number of parameters."
usage
end
## Originally, I wrote this to just do GCD, which is why there is a loop here.
## I'm too lazy to change it though.
ARGV.each do |param|
if param.to_i == 0
puts "Error: One or more parameters was not an integer, or was zero."
usage
end
end
## We can be somewhat sure that we've been supplied one integer at this point.
## So assign the value to a variable.
input = ARGV[0].to_i
## Will be what we increment from to find the coprime.
coprime_seed = 3 # Starting at 3 because why not?
## Recursive Euclidean algorithm taken from:
## http://en.wikipedia.org/wiki/Euclidean_algorithm
def gcd(a,b)
## For Debugging:
# puts "gcd(#{a},#{b})"
if b == 0
return a
else
return gcd(b, a%b)
end
end
## Two integers are defined as coprime when their greatest common divisor is
## equal to one. Therefore, it follows that if we increment from one and test
## the gcd on each loop, we will eventually find a number coprime to our input.
def find_coprime(a,z)
if gcd(a,z) == 1
return z
end
find_coprime(a, z + 1)
end
## Main:
puts "Valid coprime of #{input} is: #{find_coprime(input,coprime_seed)}."
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment