prime-tiny.rb

class Prime
  # https://oeis.org/A014233
  #
  # Smallest odd number for which Miller-Rabin primality test
  # on bases <= n-th prime does not reveal compositeness.
  #
  A014233 = {
     2 => 2047,                
     3 => 1373653,               
     5 => 25326001,             
     7 => 3215031751,         
    11 => 2152302898747,
    13 => 3474749660383,
    17 => 341550071728321,
    19 => 341550071728321,
    23 => 3825123056546413051,
    29 => 3825123056546413051,
    31 => 3825123056546413051,
    37 => 318665857834031151167461,
    41 => 3317044064679887385961981
  }
end

class Integer
  # returns +b+**+x+ % +m+
  def powmod(b, x, m)
   r = 1
   while x > 0
     r = (r * b) % m if x & 1 == 1
     b = (b * b) % m
     x >>= 1;
   end
   r
  end
  # Returns true if +self+ passes Miller-Rabin Test on +b+
  def miller_rabin_test(b)
    return false if self < 2
    return self == 2 if self & 1 == 0
    d = self - 1
    d >>= 1 while d & 1 == 0
    t = d
    y = powmod(b, t, self)
    while t != self-1 && y != 1 && y != self-1
      y = (y * y) % self
      t <<= 1
    end
    return false if y != self-1 && t & 1 == 0
    return true
  end
  # Returns true if +self+ passes Miller-Rabin Test on +b+
  def prime?
    return false if self < 2
    return self == 2 if self & 1 == 0
    return self == 3 if self % 3 == 0
    return self == 5 if self % 5 == 0
    return self == 7 if self % 7 == 0
    Prime::A014233.each do |pair|
      ix, mx = pair
      return false if miller_rabin_test(ix) == false
      break if self < mx
    end
    return miller_rabin_test(41)
  end
  # Returns the smallest prime number which is greater than +self+
  def next_prime
    return 2 if self < 2
    n = self
    n += if n & 1 == 0 then 1 else 2 end
    while !n.prime?
      n += 2
    end
    return n
  end
  # Returns the largest prime number which is smaller than +self+
  # or +nil+ if +self+ <= 2
  def prev_prime
    return nil if self <= 2
    return   2 if self == 3
    n = self
    n -= if n & 1 == 0 then 1 else 2 end
    while !n.prime?
      n -= 2
    end
    return n
  end
end