Last active
November 1, 2016 11:01
-
-
Save ktec/80ac458abab56fa9eb17 to your computer and use it in GitHub Desktop.
A class which generates the prime factors for a given number. It tries to do it in a relatively optimised way by using a lazy prime generator inside an enumerator.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Prime | |
def self.primes | |
isComposite = -> (n) {(3..Math.sqrt(n)).step(2).any?{ |i| n % i == 0 }} | |
Enumerator.new do |e| | |
e.yield 2 # start at 2 | |
(3..Float::INFINITY) # start generator from 3 | |
.step(2) # sieve all even numbers | |
.lazy # calculate on demand | |
.reject(&isComposite) # sieve all composites numbers | |
.map(&:to_i) # reduce to ints | |
.each(&e.method(:yield).to_proc) # yield only when asked | |
end.lazy | |
end | |
def self.prime_division(n, primes = Prime.primes) | |
raise ZeroDivisionError if n == 0 | |
pv = [] | |
return pv unless n > 1 | |
primes.each do |p| | |
count = 0 | |
while (quot, mod = n.divmod(p) | |
mod) == 0 | |
n = quot | |
count += 1 | |
end | |
pv.push [p, count] if count > 0 | |
break if quot <= p | |
end | |
pv.push [n, 1] if n > 1 | |
return pv | |
end | |
end | |
class PrimeFactorizer | |
def factors | |
@factors | |
end | |
private | |
def initialize(n) | |
@factors = Hash[Prime.prime_division(n)] | |
end | |
end | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Some related links:
http://www.sievesofchaos.com
https://www.jasondavies.com/primos/