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 <=' limit /*might as well crow a wee bit. */
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+10 /*well,prime counter for foundthis anotherpass. one, by gum*/
 
do a=2 to accur do z=1 for limit /*(skippingnow, 1)let's get dobusy rangeand ofcrank. K's.*/
say copies p=Miller_Rabin('-'z,79a) /*invoke and pray... /*show separator for the eyeballs*/
mrp=0 if p==0 then iterate /*Not prime? counter for thisThen passtry another. */
mrp=mrp+1 /*well, found another one, by gum*/
 
do z=1 for limit if tell then say z, /*now,maybe let'sshould do geta busyshow and& crank.tell ?*/
p=Miller_Rabin(z,a) /*invoke and pray... */
if p==0 then iterate /*Not prime? Then try another. */
mrp=mrp+1 /*well, found another one, by gum*/
 
if tell then say z, /*maybe should do a show & tell ?*/
'is prime according to Miller-Rabin primality test with K='a
 
if !.z\==0 then iterate
say '[K='ka"] " z "isn't prime !" /*oopsy-doopsy and& whoopsy-daisy!*/
end /*z*/
 
say 'for 1-->1──►'limit", K="ka', Miller-Rabin primality test found' mrp,
'primes {out of' primePi"}"
end /*a*/
exit /*stick a fork in it, we're done.*/
 
/*─────────────────────────────────────Miller─Rabin primality test.─────*/
exit
/*─────────────────────────────────────Rabin─Miller (also known as)─────*/
/*─────────────────────────────────────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 /*while d//2==0 */
 
do k
a=random(2,nL)
x=(a**d) // n /*this number can get big fast. */
if x==1 | x==nL then iterate
 
do r=1 for s-1
x do r=(x*x)1 //for ns-1
if x==1 then return 0 x=(x*x) /*definately/ it's not prime. */n
if x==nL1 then leavereturn 0 /*it's definately not prime. */
end if x==nL then leave
end /*kr*/
if x\==nL then return 0
 
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 subroutine────────────*/
suspenders: @.=0; !.=0 /*crank up the ole prime factory.*/
@.1=2; @.2=3; @.3=5; #=3 /*prime the pump with low primes.*/
!.2=1; !.3=1; !.5=1 /*and don't forget the water jar.*/
 
do j=@.#+2 by 2 to limit /*just process the odd integers. */
do k=2j while =@.k**#+2<=j by 2 to limit /*let'sjust doprocess the oleodd primalityintegers. test*/
if j//@. do k==0 then2 iteratewhile @.k**2<=j /*thelet's Greekdo way,the inole daysprimality of yore.test*/
end if j/*/@.k*/ ==0 then iterate j /*athe uselessGreek commentway, but hey!!in days of yore.*/
#=#+1 end /*k*/ /*bump the prime counter. a useless comment, but hey!! */
@.#=j #=#+1 /*keep primingbump the prime pumpcounter. */
!.j=1 @.#=j /*and keep fillingpriming the waterprime jarpump. */
end !.j=1 /*j*/ /*thisand commentkeep notfilling leftthe blankwater jar. */
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 <= 10000
 
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
[K=2] 2701 isn't prime !
for 1-->100001──►10000, K=2, Miller-RabinMiller─Rabin primality test found 1230 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->100001──►10000, K=2, Miller-RabinMiller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->100001──►10000, K=3, Miller-RabinMiller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->100001──►10000, K=4, Miller-RabinMiller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->100001──►10000, K=5, Miller-RabinMiller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->100001──►10000, K=6, Miller-RabinMiller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->100001──►10000, K=7, Miller-RabinMiller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->100001──►10000, K=8, Miller-RabinMiller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->100001──►10000, K=9, Miller-RabinMiller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->100001──►10000, K=10, Miller-RabinMiller─Rabin primality test found 1229 primes {out of 1229}
</pre>