Module: FasterPrime::PrimeFactorization

Defined in:
lib/faster_prime/prime_factorization.rb

Class Method Summary collapse

Class Method Details

.prime_factorization(n) ⇒ Object

Factorize an integer



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/faster_prime/prime_factorization.rb', line 8

def prime_factorization(n)
  return enum_for(:prime_factorization, n) unless block_given?

  return if n == 0
  if n < 0
    yield [-1, 1]
    n = -n
  end

  SMALL_PRIMES.each do |prime|
    if n % prime == 0
      c = 0
      begin
        n /= prime
        c += 1
      end while n % prime == 0
      yield [prime, c]
    end
    if prime * prime > n
      yield [n, 1] if n > 1
      return
    end
    return if n == 1
  end

  if PrimalityTest.prime?(n)
    yield [n, 1]
  else
    d = nil
    until d
      [PollardRho, MPQS].each do |algo|
        begin
          d = algo.try_find_factor(n)
        rescue Failed
        else
          break
        end
      end
    end

    pe = Hash.new(0)
    prime_factorization(n / d) {|p, e| pe[p] += e }
    prime_factorization(d) {|p, e| pe[p] += e }
    pe.keys.sort.each do |p|
      yield [p, pe[p]]
    end
  end
end