Anonymous user
Sequence of primorial primes: Difference between revisions
→{{header|Ruby}}
m (changed the category name.) |
|||
Line 2,749:
<pre>
1, 2, 3, 4, 5, 6, 11, 13, 24, 66, 68, 75, 167, 171, 172, 287, 310, 352, 384, 457
</pre>
=={{header|Ruby}}==
<lang Ruby>
# Sequence of primorial primes with Miller–Rabin primality test
# I found that using only standard Class Prime.prime?(), indeed produce very short-line of code but stacked on Primorial Prime
# sequence 8 with JRuby or standard Ruby. So here I adopt RUby code for Miller–Rabin_primality_test from
# https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#This_is_a_correct_M-R_test_implementation_for_using_bases_.3E_input._3
# From output, using Ruby-MR test took time 34.011 sec to finish which by Python code (in this page) took 289.50 sec on same computer.
require 'prime'
require "openssl" # for fast n.to_bn.mod_exp(exponent, modulus) method
i, urutan, primorial_number, jml = 1, 1, 1, 500
start = Time.now
prime_array = Prime.first (jml)
# Begin code for Miller–Rabin_primality_test ..........................
class Integer
# Returns true if +self+ is a prime number, else returns false.
def primemr?
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
return primes.include? self if self <= primes.last
modp47 = 614_889_782_588_491_410 # => primes.reduce(:*), largest < 2^64
return false if self.gcd(modp47) != 1 # eliminates 86.2% of all integers
# Choose witness bases for input; wits = [range, [wit_bases]] or nil
wits = WITNESS_RANGES.find {|range, wits| range > self}
witnesses = wits && wits[1] || primes
miller_rabin_test(witnesses)
end
private
# Returns true if +self+ passes Miller-Rabin Test with witness bases +b+
def miller_rabin_test(witnesses) # use witness list to test with
neg_one_mod = n = d = self - 1 # these are even as 'self' always odd
d >>= 4 while (d & 0xf) == 0 # suck out factors of 2
(d >>= (d & 3)^2; d >>= (d & 1)^1) if d.even? # 4 bits at a time
witnesses.each do |b| # do M-R test with each witness base
next if (b % self) == 0 # **skip base if a multiple of input**
s = d
y = b.to_bn.mod_exp(d, self) # y = (b**d) mod self
until s == n || y == 1 || y == neg_one_mod
y = y.mod_exp(2, self) # y = (y**2) mod self
s <<= 1
end
return false unless y == neg_one_mod || s.odd?
end
true
end
# Best known deterministic witnesses for given range and set of bases
# https://miller-rabin.appspot.com/
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
WITNESS_RANGES = {
341_531 => [9345883071009581737],
1_050_535_501 => [336781006125, 9639812373923155],
350_269_456_337 => [4230279247111683200, 14694767155120705706, 16641139526367750375],
55_245_642_489_451 => [2, 141889084524735, 1199124725622454117, 11096072698276303650],
7_999_252_175_582_851 => [2, 4130806001517, 149795463772692060, 186635894390467037,
3967304179347715805],
585_226_005_592_931_977 => [2, 123635709730000, 9233062284813009, 43835965440333360,
761179012939631437, 1263739024124850375],
18_446_744_073_709_551_615 => [2, 325, 9375, 28178, 450775, 9780504, 1795265022],
318_665_857_834_031_151_167_461 => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37],
3_317_044_064_679_887_385_961_981 => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
}
end
# End code for Miller–Rabin_primality_test ..........................
until urutan > 20
primorial_number *= prime_array[i-1]
if (primorial_number - 1).primemr? || (primorial_number + 1).primemr?
puts "#{Time.now - start} \tPrimorial prime #{urutan}: #{i}"
urutan += 1
end
i += 1
end
</lang>
Output:
<pre>
0.052 Primorial prime 1: 1
0.056 Primorial prime 2: 2
0.058 Primorial prime 3: 3
0.061 Primorial prime 4: 4
0.063 Primorial prime 5: 5
0.064 Primorial prime 6: 6
0.071 Primorial prime 7: 11
0.074 Primorial prime 8: 13
0.091 Primorial prime 9: 24
0.185 Primorial prime 10: 66
0.207 Primorial prime 11: 68
0.252 Primorial prime 12: 75
1.006 Primorial prime 13: 167
1.129 Primorial prime 14: 171
1.21 Primorial prime 15: 172
4.933 Primorial prime 16: 287
6.9 Primorial prime 17: 310
11.51 Primorial prime 18: 352
16.655 Primorial prime 19: 384
34.011 Primorial prime 20: 457
</pre>
| |||