Rosetta Code

Carmichael 3 strong pseudoprimes: Difference between revisions

Page Discussion

Carmichael 3 strong pseudoprimes (view source)

Revision as of 16:29, 27 September 2014

254 bytes added ,  9 years ago
m
→‎{{header|REXX}}: changed some comments, used better variable names, optimized some code.
m (→‎{{header|REXX}}: restricted search list (for output) to start with the current prime.)
m (→‎{{header|REXX}}: changed some comments, used better variable names, optimized some code.)
Line 787:
 
=={{header|REXX}}==
Note that REXX's version of &nbsp; '''modulus''' &nbsp; (<big><code>'''//'''</code></big>) &nbsp; is really a &nbsp; ''remainder'' &nbsp; function,
<br>so a version of the &nbsp; '''modulus''' &nbsp; function was hard-coded below.
<br>(It was necessary to use '''modulus''' instead of '''remainder''' when using a negative value.)
 
<br>The Carmichael numbers are shown in numerical order.
<br>Some code optimization was done, while not necessary for the small default number (<code>61</code>), it was significant for larger numbers.
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes (up to N).*/
numeric digits 30 /*in case user wants bigger nums.*/
Line 800 ⟶ 801:
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1; !.23=1
/*[↓] prime # memoization array.*/
do p=3 to N by 2; if \isPrime(p) then iterate /*Not prime? Skip.*/
pm=p-1; nps=-p*p; @. bot=0; maxtop=0 /*some handy-dandy REXX variables*/
@.=0 /*[↑] Carmichael numbers are odd*/
do h3=2 to pm; g=h3+p /*find Carmichael #s for this P. */
gpmgPM=g*pm; npsh3 npsH3=((nps//h3)+h3)//h3 /*shortcut stuffshortcuts. */
 
do d=1 for g-1▼
if gpm //do d \== 0 1 thenfor iterateg-1
if npsh3gPM//d \== 0 \== d//h3 then iterate
q if npsH3 \=1+gpm%= d;//h3 if \isPrime(q) then iterate
r q=1+p*qgPM%h3d; if \isPrime(q*r//pm\==1) then iterate
r=1+p*q%h3; if q*r//pm\isPrime(r)==1 then iterate
carms=carms+1 /*bump the Carmichael # counter. */if \isPrime(r) then iterate
max carms=max(max,q)carms+1; @.q=r /*findbump theCarmichael maximum,#; buildadd ato list.array*/
end if bot==0 /*d*/ then bot=q; bot=min(bot,q); top=max(top,q)
/*find the maximum. end /*h3*/
end /*d*/ /* [↑] find minimum and maximum.*/
▲ end do d=1 for g-1/*h3*/
$=0 /*display a list of some Carm #s.*/
do j=pbot to maxtop by 2; if @.j==0 then iterate; $=1
say '──────── a Carmichael number: ' p times j times @.j
end /*j*/
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/222710"