Skip to content

Instantly share code, notes, and snippets.

@havenwood
Created October 13, 2022 22:49
Show Gist options
  • Save havenwood/c1931cec804c09fd28193606d42a6c51 to your computer and use it in GitHub Desktop.
Save havenwood/c1931cec804c09fd28193606d42a6c51 to your computer and use it in GitHub Desktop.
Comparing 42.prime? to Prime.prime?(42) for Ruby IRC
class Integer
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
end
class Prime
class << self
def prime?(value, generator = Prime::Generator23.new)
raise ArgumentError, "Expected a prime generator, got #{generator}" unless generator.respond_to? :each
raise ArgumentError, "Expected an integer, got #{value}" unless value.respond_to?(:integer?) && value.integer?
return false if value < 2
generator.each do |num|
q,r = value.divmod num
return true if q < num
return false if r == 0
end
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment