32 
32 

33 
33 
# Returns true if +self+ is a prime number, else returns false.

34 
34 
def prime?

35 

return self >= 2 if self <= 3

36 

return true if self == 5

37 

return false unless 30.gcd(self) == 1

38 

(7..Integer.sqrt(self)).step(30) do p

39 

return false if

40 

self%(p) == 0  self%(p+4) == 0  self%(p+6) == 0  self%(p+10) == 0 

41 

self%(p+12) == 0  self%(p+16) == 0  self%(p+22) == 0  self%(p+24) == 0

42 

end

43 

true


35 
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test


36 
# https://arxiv.org/pdf/1509.00864.pdf


37 
#


38 
# if n < 3,317,044,064,679,887,385,961,981,


39 
# it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.


40 
# and the result will be deterministic.


41 
#


42 


43 
if self > 3317044064679887385961981


44 
raise ArgumentError, ".prime? is only valid for values less than 3,317,044,064,679,887,385,961,981"


45 
end


46 


47 
return false if self < 2


48 
return true if self < 4


49 
return false if self.even?


50 


51 
r = 0


52 
d = self  1


53 


54 
while d.even?


55 
d /= 2


56 
r += 1


57 
end


58 


59 
[2,3,5,7,11,13,17,19,23,29,31,37,41].each do a


60 
x = a.pow(d, self)


61 
next if x == 1  x == (self1)  a == self


62 


63 
(r1).times do


64 
x = x.pow(2, self)


65 
if x == (self1)


66 
break


67 
end


68 
end


69 


70 
if (x == self1)


71 
next


72 
else


73 
return false


74 
end


75 
end


76 
return true

44 
77 
end

45 
78 

46 
79 
# Iterates the given block over all prime numbers.
