class Integer

# File prime.rb, line 122
def Integer.each_prime(ubound, &block) # :yields: prime
  Prime.each(ubound, &block)
end

# File prime.rb, line 22
def Integer.from_prime_division(pd)
  Prime.int_from_prime_division(pd)
end

# File prime.rb, line 35
def prime?
  return self >= 2 if self <= 3

  if (bases = miller_rabin_bases)
    return miller_rabin_test(bases)
  end

  return true if self == 5
  return false unless 30.gcd(self) == 1
  (7..Integer.sqrt(self)).step(30) do |p|
    return false if
      self%(p)    == 0 || self%(p+4)  == 0 || self%(p+6)  == 0 || self%(p+10) == 0 ||
      self%(p+12) == 0 || self%(p+16) == 0 || self%(p+22) == 0 || self%(p+24) == 0
  end
  true
end

# File prime.rb, line 29
def prime_division(generator = Prime::Generator23.new)
  Prime.prime_division(self, generator)
end

# File prime.rb, line 69
        def miller_rabin_bases
  # Miller-Rabin's complexity is O(k log^3n).
  # So we can reduce the complexity by reducing the number of bases tested.
  # Using values from https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
  i = case
  when self < 0xffff                            then
    # For small integers, Miller Rabin can be slower
    # There is no mathematical significance to 0xffff
    return nil
# when self < 2_047                             then 0
  when self < 1_373_653                         then 1
  when self < 9_080_191                         then 2
  when self < 25_326_001                        then 3
  when self < 3_215_031_751                     then 4
  when self < 4_759_123_141                     then 5
  when self < 1_122_004_669_633                 then 6
  when self < 2_152_302_898_747                 then 7
  when self < 3_474_749_660_383                 then 8
  when self < 341_550_071_728_321               then 9
  when self < 3_825_123_056_546_413_051         then 10
  when self < 318_665_857_834_031_151_167_461   then 11
  when self < 3_317_044_064_679_887_385_961_981 then 12
  else return nil
  end
  MILLER_RABIN_BASES[i]
end

# File prime.rb, line 96
        def miller_rabin_test(bases)
  return false if even?

  r = 0
  d = self >> 1
  while d.even?
    d >>= 1
    r += 1
  end

  self_minus_1 = self-1
  bases.each do |a|
    x = a.pow(d, self)
    next if x == 1 || x == self_minus_1 || a == self

    return false if r.times do
      x = x.pow(2, self)
      break if x == self_minus_1
    end
  end
  true
end