Skip to content

Instantly share code, notes, and snippets.

@carbonphyber
Created April 30, 2011 20:19
Show Gist options
  • Save carbonphyber/949961 to your computer and use it in GitHub Desktop.
Save carbonphyber/949961 to your computer and use it in GitHub Desktop.
Ruby function to detect if a Fixednum is a prime number
# @author David Wortham <djwortham+programming@gmail.com>
# @date 2011-04-30
# @license MIT License: http://www.opensource.org/licenses/mit-license.php
# isPrime
# Function to detect if the input (asserted Fixednum) is a prime number
# uses an optional cache (asserted Hash) to speed up subsequent calls
def isPrime(number, cache)
return false if number < 1
return true if number == 1
# if our cache contains the result for this number, then just use the cached result
return cache[number] unless cache.nil? || cache[number].nil?
# there is no need to test numbers larger than (number + 1) / 2 for prime factors
maxTest = (number + 1) / 2
i = 2
# no reason to retest numbers we already have cached; need to check to make sure this method is optimal
unless cache.nil? || cache.empty?
i = cache.length
end
while i < maxTest
if number % i == 0
cache[number] = false unless cache.nil?
return false
else
cache[number] = true unless cache.nil?
end
i = i + 1
end
return true
end
# usage (without cache):
# puts "is 19 prime? #{isPrime(19)}"
# usage (with cache):
# primeCache = {}
# puts "is 34 prime? #{isPrime(34, primeCache)}"
# puts "is 19 prime? #{isPrime(19, primeCache)}" # this result has already been cached by the previous call
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment