Anonymous user
Miller–Rabin primality test: Difference between revisions
m
→{{header|REXX}}: changed the separator fence, indented DO loops more, added DO-END comment labels. -- ~~~~
(→{{header|Go}}: added deterministic test) |
m (→{{header|REXX}}: changed the separator fence, indented DO loops more, added DO-END comment labels. -- ~~~~) |
||
Line 1,536:
call suspenders /*suspenders now, belt later... */
primePi=# /*save the count of (real) primes*/
say "They're" primePi 'primes
say /*nothing wrong with whitespace. */
do a=2 to accur /*(skipping 1) do range of K's.*/
say copies('─',79) /*show separator for the eyeballs*/
mrp=mrp+1 /*well, found another one, by gum*/
▲ mrp=mrp+1 /*well, found another one, by gum*/
'is prime according to Miller-Rabin primality test with K='a
if !.z\==0 then iterate
say '[K='
end /*z*/
say 'for
'primes {out of' primePi"}"
end /*a*/
exit /*stick a fork in it, we're done.*/
/*─────────────────────────────────────Miller─Rabin primality test.─────*/
/*─────────────────────────────────────Rabin─Miller (also known as)─────*/
Miller_Rabin: procedure; parse arg n,k
if n==2 then return 1 /*special case of an even prime. */
Line 1,569 ⟶ 1,567:
s=0
do while d//2==0; d=d%2; s=s+1; end
do k
a=random(2,nL)
x=(a**d) // n
if x==1 | x==nL then iterate
if x==
▲ end /*k*/
if x\==nL then return 0 /*nope, it ain't prime nohows. */
end /*k*/
/*maybe it is, maybe it ain't ...*/
return 1 /*coulda/woulda/shoulda be prime.*/
/*──────────────────────────────────SUSPENDERS subroutine───────────────*/
suspenders: @.=0; !.=0
@.1=2; @.2=3; @.3=5; #=3
!.2=1; !.3=1; !.5=1
do
end /*j*/ /*this comment not left blank. */
return /*whew! All done with the primes*/</lang>
{{out|Output when using the input of: <tt>10000 10</tt>}}
<pre style="height:30ex;overflow:scroll">
They're 1229 primes
───────────────────────────────────────────────────────────────────────────────
[K=2] 2701 isn't prime !
for
───────────────────────────────────────────────────────────────────────────────
for
───────────────────────────────────────────────────────────────────────────────
for
───────────────────────────────────────────────────────────────────────────────
for
───────────────────────────────────────────────────────────────────────────────
for
───────────────────────────────────────────────────────────────────────────────
for
───────────────────────────────────────────────────────────────────────────────
for
───────────────────────────────────────────────────────────────────────────────
for
───────────────────────────────────────────────────────────────────────────────
for
───────────────────────────────────────────────────────────────────────────────
for
</pre>
|