Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (→{{Header|OCaml}}: minor clarifications and improvements) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
Line 3,818: | Line 3,818: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|C}} |
|||
=== native, determinstic to 94,910,107 === |
=== 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], |
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. |
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> |
<!--<lang Phix>(phixonline)--> |
||
<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}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,900: | Line 3,903: | ||
</pre> |
</pre> |
||
=== gmp version === |
=== gmp version, deterministic to 3,317,044,064,679,887,385,961,981 === |
||
{{libheader|Phix/mpfr}} |
{{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 < 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 >>= 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</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 << 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> |
</pre> |
||