Rosetta Code

Miller–Rabin primality test: Difference between revisions

Page Discussion

Miller–Rabin primality test (view source)

Revision as of 03:52, 8 June 2021

47,822 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{Header|OCaml}}: minor clarifications and improvements)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 3,818:
 
=={{header|Phix}}==
{{trans|C}}
=== native, determinstic to 94,910,107 ===
{{trans|C}}
Native-types deterministic version, fails (false negative) at 94,910,107 on 32-bit [fully tested, ie from 1],
and at 4,295,041,217 on 64-bit [only tested from 4,290,000,000] - those limits have now been hard-coded below.
<!--<lang Phix>function powermod(atom a, atom n, atom mphixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
-- calculate a^n%mod
<span style="color: #008080;">function</span> <span style="color: #000000;">powermod</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
atom p = a, res = 1
<span style="color: #000080;font-style:italic;">-- calculate a^n%mod</span>
while n do
<span style="color: #004080;">atom</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
if and_bits(n,1) then
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
res = mod(res*p,m)
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
p = mod(p*p,m)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
n = floor(n/2)
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
end while
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function witness(atom n, atom s, atom d, sequence a)
-- n-1 = 2^s * d with d odd by factoring powers of 2 from n-1
<span style="color: #008080;">function</span> <span style="color: #000000;">witness</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
for i=1 to length(a) do
<span style="color: #000080;font-style:italic;">-- n-1 = 2^s * d with d odd by factoring powers of 2 from n-1</span>
atom x = powermod(a[i], d, n), y, w=s
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
while w do
<span style="color: #004080;">atom</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">powermod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">=</span><span style="color: #000000;">s</span>
y = mod(x*x,n)
<span style="color: #008080;">while</span> <span style="color: #000000;">w</span> <span style="color: #008080;">do</span>
if y == 1 and x != 1 and x != n-1 then
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
return false
<span style="color: #008080;">if</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
end if
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
x = y
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
w -= 1
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span>
end while
<span style="color: #000000;">w</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
if y != 1 then
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return false
<span style="color: #008080;">if</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
end if
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return true;
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function is_prime_mr(atom n)
if (mod(n,2)==0 and n!=2)
<span style="color: #008080;">function</span> <span style="color: #000000;">is_prime_mr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
or (n<2)
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
or (mod(n,3)==0 and n!=3) then
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
return false
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
elsif n<=3 then
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
return true
<span style="color: #008080;">elsif</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span>
end if
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
atom d = floor(n/2)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
atom s = 1;
<span style="color: #004080;">atom</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
while and_bits(d,1)=0 do
<span style="color: #004080;">atom</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span>
d /= 2
<span style="color: #008080;">while</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
s += 1
<span style="color: #000000;">d</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">2</span>
end while
<span style="color: #000000;">s</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
sequence a
if n < 1373653 then
<span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span>
a = {2, 3}
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">1373653</span> <span style="color: #008080;">then</span>
elsif n < 9080191 then
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">}</span>
a = {31, 73}
<span style="color: #008080;">elsif</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">9080191</span> <span style="color: #008080;">then</span>
elsif (machine_bits()=32 and n < 94910107)
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">31</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">73</span><span style="color: #0000FF;">}</span>
or (machine_bits()=64 and n < 4295041217) then
<span style="color: #008080;">elsif</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">94910107</span><span style="color: #0000FF;">)</span>
a = {2, 7, 61}
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">64</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">4295041217</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">61</span><span style="color: #0000FF;">}</span>
puts(1,"limits exceeded\n")
<span style="color: #008080;">else</span>
return 0
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"limits exceeded\n"</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
return witness(n, s, d, a)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">witness</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
sequence tests = {999983,999809,999727,52633,60787,999999,999995,999991}
for i=1 to length(tests) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">999983</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999809</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999727</span><span style="color: #0000FF;">,</span><span style="color: #000000;">52633</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60787</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999999</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999995</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999991</span><span style="color: #0000FF;">}</span>
printf(1,"%d is %s\n",{tests[i],{"composite","prime"}[is_prime_mr(tests[i])+1]})
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for</lang>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d is %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],{</span><span style="color: #008000;">"composite"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"prime"</span><span style="color: #0000FF;">}[</span><span style="color: #000000;">is_prime_mr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Line 3,900 ⟶ 3,903:
</pre>
 
=== gmp version, deterministic to 3,317,044,064,679,887,385,961,981 ===
{{libheader|Phix/mpfr}}
{{trans|Ruby}}
completes near-instantly
While desktop/Phix uses a thin wrapper to the builtin gmp routine, the following is also available and is used (after transpilation) in mpfr.js, renamed as mpz_prime:
<lang Phix>include mpfr.e
<!--<lang Phix>(phixonline)-->
mpz b = mpz_init()
<span style="color: #000080;font-style:italic;">-- this is transpiled (then manually copied) to mpz_prime() in mpfr.js:</span>
randstate state = gmp_randinit_mt()
<span style="color: #004080;">mpz</span> <span style="color: #000000;">modp47</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">witness_ranges</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">mpz_prime_mr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- deterministic to 3,317,044,064,679,887,385,961,981</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">13</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">29</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">31</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">37</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">41</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">43</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">47</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">[$])<=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">modp47</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">modp47</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"614_889_782_588_491_410"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- === product(primes), largest &lt; 2^64</span>
<span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- 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</span>
<span style="color: #000000;">witness_ranges</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"341_531"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"9345883071009581737"</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"1_050_535_501"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"336781006125"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"9639812373923155"</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"350_269_456_337"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"4230279247111683200"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"14694767155120705706"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"16641139526367750375"</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"55_245_642_489_451"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"2"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"141889084524735"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"1199124725622454117"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"11096072698276303650"</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"7_999_252_175_582_851"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"2"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"4130806001517"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"149795463772692060"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"186635894390467037"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"3967304179347715805"</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"585_226_005_592_931_977"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"2"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"123635709730000"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"9233062284813009"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"43835965440333360"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"761179012939631437"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"1263739024124850375"</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"18_446_744_073_709_551_615"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"2"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"325"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"9375"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"28178"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"450775"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"9780504"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"1795265022"</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"318_665_857_834_031_151_167_461"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"2"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"3"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"5"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"7"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"11"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"13"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"17"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"19"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"23"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"29"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"31"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"37"</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"3_317_044_064_679_887_385_961_981"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"2"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"3"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"5"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"7"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"11"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"13"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"17"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"19"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"23"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"29"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"31"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"37"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"41"</span><span style="color: #0000FF;">}}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">modp47</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #000080;font-style:italic;">-- eliminates 86.2% of all integers</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">--
-- Choose input witness bases:
--</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">witnesses</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">[$][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])>=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">witnesses</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">k</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_sub_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- a := 0..a-1 (cf rand(n) yields 1..n)</span>
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">witnesses</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])<</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">witnesses</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">witness_ranges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_sub_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">nm1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- d &gt;&gt;= 4 while (d & 0xf) == 0 # suck out factors of 2
-- (d &gt;&gt;= (d & 3)^2; d &gt;&gt;= (d & 1)^1) if d.even? # 4 bits at a time</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_fdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">witnesses</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">witnesses</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">mpz_divisible_p</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- skip multiples of input</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- y := b^d % p</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span>
<span style="color: #008080;">and</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nm1</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span>
<span style="color: #008080;">and</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nm1</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_powm_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- y := y^2 mod p</span>
<span style="color: #7060A8;">mpz_mul_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- s &lt;&lt; 1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nm1</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</lang>-->
Either the standard shim or the above can be used as follows
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"9223372036854774808"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">4808</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5808</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (b ends thus)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %s%s"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n%d primes found\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"4547337172376300111955330758342147474062293202868155909489"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"4547337172376300111955330758342147474062293202868155909393"</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_set_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)?</span><span style="color: #008000;">"is prime"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"is composite"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s %s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1300</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"2^%d-1 is prime\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
  9223372036854774893  9223372036854774917  9223372036854774937  9223372036854774959  9223372036854775057
  9223372036854775073  9223372036854775097  9223372036854775139  9223372036854775159  9223372036854775181
  9223372036854775259  9223372036854775279  9223372036854775291  9223372036854775337  9223372036854775351
  9223372036854775399  9223372036854775417  9223372036854775421  9223372036854775433  9223372036854775507
  9223372036854775549  9223372036854775643  9223372036854775783
23 primes found
 
4547337172376300111955330758342147474062293202868155909489 is prime
mpz_set_str(b,"9223372036854774808")
integer c = 0
for i=4808 to 5808 do -- (b ends thus)
if mpz_probable_prime_p(b,state) then
c += 1
printf(1," %s%s",{mpz_get_str(b),"\n"[1..mod(c,5)=0]})
end if
mpz_add_ui(b,b,1)
end for
printf(1,"\n%d primes found\n\n",c-1)
 
4547337172376300111955330758342147474062293202868155909393 is composite
constant tests = {"4547337172376300111955330758342147474062293202868155909489",
"4547337172376300111955330758342147474062293202868155909393"}
for i=1 to length(tests) do
mpz_set_str(b,tests[i])
string p = iff(mpz_probable_prime_p(b,state)?"is prime":"is composite")
printf(1,"%s %s\n",{tests[i],p})
end for
 
for i=2 to 1300 do
mpz_ui_pow_ui(b,2,i)
mpz_sub_si(b,b,1)
if mpz_probable_prime_p(b,state) then
printf(1,"2^%d-1 is prime\n",{i})
end if
end for</lang>
{{out}}
<pre>
9223372036854774893 9223372036854774917 9223372036854774937 9223372036854774959 9223372036854775057
9223372036854775073 9223372036854775097 9223372036854775139 9223372036854775159 9223372036854775181
9223372036854775259 9223372036854775279 9223372036854775291 9223372036854775337 9223372036854775351
9223372036854775399 9223372036854775417 9223372036854775421 9223372036854775433 9223372036854775507
9223372036854775549 9223372036854775643 9223372036854775783
23 primes found
 
2^2-1 is prime
4547337172376300111955330758342147474062293202868155909489 is prime
2^3-1 is prime
4547337172376300111955330758342147474062293202868155909393 is composite
2^5-1 is prime
2^2-1 is prime
2^7-1 is prime
2^3-1 is prime
2^13-1 is prime
2^5-1 is prime
2^17-1 is prime
2^7-1 is prime
2^19-1 is prime
2^13-1 is prime
2^31-1 is prime
2^17-1 is prime
2^61-1 is prime
2^19-1 is prime
2^89-1 is prime
2^31-1 is prime
2^107-1 is prime
2^61-1 is prime
2^127-1 is prime
2^89-1 is prime
2^521-1 is prime
2^107-1 is prime
2^607-1 is prime
2^127-1 is prime
2^1279-1 is prime
2^521-1 is prime
2^607-1 is prime
2^1279-1 is prime
</pre>
 
Petelomax
7,794

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/108046"