Method: Prime#prime_division

Defined in:
lib/prime.rb

#prime_division(value, generator = Prime::Generator23.new) ⇒ Object

Returns the factorization of value.

For an arbitrary integer:

p_1**e_1 * p_2**e_2 * ... * p_n**e_n,

prime_division returns an array of pairs of integers:

[[p_1, e_1], [p_2, e_2], ..., [p_n, e_n]].

Each pair consists of a prime number – a prime factor – and a natural number – its exponent (multiplicity).

Parameters

value

An arbitrary integer.

generator

Optional. A pseudo-prime generator. generator.succ must return the next pseudo-prime number in ascending order. It must generate all prime numbers, but may also generate non-prime numbers, too.

Exceptions

ZeroDivisionError

when value is zero.

Example

Prime.prime_division(45)  #=> [[3, 2], [5, 1]]
3**2 * 5                  #=> 45

Raises:

  • (ZeroDivisionError) 

303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
 
# File 'lib/prime.rb', line 303

def prime_division(value, generator = Prime::Generator23.new)
  raise ZeroDivisionError if value == 0
  if value < 0
    value = -value
    pv = [[-1, 1]]
  else
    pv = []
  end
  generator.each do |prime|
    count = 0
    while (value1, mod = value.divmod(prime)
           mod) == 0
      value = value1
      count += 1
    end
    if count != 0
      pv.push [prime, count]
    end
    break if value1 <= prime
  end
  if value > 1
    pv.push [value, 1]
  end
  pv
end