# Copyright 2005 Justin W. Smith # Distributed under the terms of the BSD License class Primes include Math include Enumerable def initialize(max = 1000) @max = max @primes = [2, 3] end attr_reader(:max) def max=(x) if x < @max @primes.reverse_each do |prime| if prime > x @primes.pop end end end @max = x end def check_primes(x) sqrtx = sqrt(x) @primes.each do |val| if val <= sqrtx if x % val == 0 return val end else return x end end x end def each() done = false i = 0 @primes.each do |prime| yield prime i += 1 end candidate = @primes.last # if the user "broke out" of the prior loop then don't continue the loop if i == @primes.length loop do candidate += 2 (candidate += 2) if (candidate % 3 == 0) # seems to improve speed slightly break if candidate > @max if check_primes(candidate) == candidate @primes.push candidate yield candidate end end end end def factor(x) raise(RuntimeException, "Cannot find prime factors for a number larger than the square of the max: #{@max} ") if x > (@max ** 2) factors = [] sqrtx = sqrt(x) each do |prime| if prime > sqrtx break end if x % prime == 0 factors.push prime x /= prime redo end end factors.push x if x > 1 factors end private :check_primes end