Skip to content

Instantly share code, notes, and snippets.

@rskvirskiy
Last active August 29, 2015 14:17
Show Gist options
  • Save rskvirskiy/fdb5c3857026cccfbbdf to your computer and use it in GitHub Desktop.
Save rskvirskiy/fdb5c3857026cccfbbdf to your computer and use it in GitHub Desktop.
Prime Factorization without usage 'prime' lib
class PrimeFactorizer
attr_reader :number
def initialize(number)
check_argument(number)
@number = number
end
def factors
@factors ||= search_factors
end
private
def search_factors
divided_number = number
result_array = []
prime = Prime.new
current_prime = prime.next
while divided_number > 1
if divided_number % current_prime == 0
divided_number /= current_prime
result_array << current_prime
else
current_prime = prime.next
end
end
result_array.each_with_object(Hash.new(0)) { |prime, hash| hash[prime] += 1 }
end
def check_argument(number)
unless number.is_a? Fixnum
throw ArgumentError, 'argument should be Fixnum number'
end
if number < 2
throw ArgumentError, 'argument should be greater than 1'
end
end
end
class Prime
attr_reader :temp_primes
def initialize
@temp_primes = []
end
def next
if temp_primes.empty?
@temp_primes << 2
return 2
end
current_number = temp_primes.last + 1
until prime? current_number
current_number += 1
end
@temp_primes << current_number
current_number
end
private
def prime?(number)
temp_primes.each do |prime|
return false if number % prime == 0
end
true
end
end
@akisel
Copy link

akisel commented Mar 24, 2015

Alternative for prime?
def prime?
!temp_primes.any?{|prime| (number % prime) .zero? }
#temp_primes.all?{|prime| (number % prime) != 0 }
end

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment