Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (→{{header|Ada}}: fixed a typ) |
(Added Bracmat) |
||
Line 407: | Line 407: | ||
} |
} |
||
quit</lang> |
quit</lang> |
||
=={{header|Bracmat}}== |
|||
{{trans|bc}} |
|||
<lang bracmat>( 1:?seed |
|||
& ( rand |
|||
= |
|||
. mod$(!seed*1103515245+12345.4294967296):?seed |
|||
& mod$(div$(!seed.65536).32768) |
|||
) |
|||
& ( rangerand |
|||
= from to b h i m n r length |
|||
. !arg:(?from,?to) |
|||
& !to+-1*!from+1:?m |
|||
& @(!m:? [?length) |
|||
& div$(!length+1.2)+1:?h |
|||
& 100^mod$(!h.!m):?b |
|||
& whl |
|||
' ( 0:?n |
|||
& !h+1:?i |
|||
& whl |
|||
' ( !i+-1:>0:?i |
|||
& rand$:?r |
|||
& whl'(!r:<68&rand$:?r) |
|||
& !n*100+mod$(!r.100):?n |
|||
) |
|||
& !n:>!b |
|||
) |
|||
& !from+mod$(!n.!m) |
|||
) |
|||
& ( miller-rabin-test |
|||
= n k d r a x s return |
|||
. !arg:(?n,?k) |
|||
& ( !n:~>3&1 |
|||
| mod$(!n.2):0 |
|||
| !n+-1:?d |
|||
& 0:?s |
|||
& whl |
|||
' ( mod$(!d.2):0 |
|||
& !d*1/2:?d |
|||
& 1+!s:?s |
|||
) |
|||
& 1:?return |
|||
& whl |
|||
' ( !k+-1:?k:~<0 |
|||
& rangerand$(2,!n+-2):?a |
|||
& mod$(!a^!d.!n):?x |
|||
& ( !x:1 |
|||
| 0:?r |
|||
& whl |
|||
' ( !r+1:~>!s:?r |
|||
& !n+-1:~!x |
|||
& mod$(!x*!x.!n):?x |
|||
) |
|||
& ( !n+-1:!x |
|||
| 0:?return&~ |
|||
) |
|||
) |
|||
) |
|||
& !return |
|||
) |
|||
) |
|||
& 0:?i |
|||
& :?primes |
|||
& whl |
|||
' ( 1+!i:<1000:?i |
|||
& ( miller-rabin-test$(!i,10):1 |
|||
& !primes !i:?primes |
|||
| |
|||
) |
|||
) |
|||
& !primes:? [-11 ?last |
|||
& out$!last |
|||
);</lang> |
|||
output: |
|||
<pre>937 941 947 953 967 971 977 983 991 997</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
{{libheader|GMP}} |
{{libheader|GMP}} |