Carmichael 3 strong pseudoprimes: Difference between revisions

<br>Some code optimization was done, while not necessary for the small default number (<code>'''61</code>'''), &nbsp; it was significant for larger numbers.

<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes (up to and including N). */

numeric digits 30 /*inhandle big dig case#s user(9 wantsis biggerthe numsdefault).*/

parse arg N .; if N=='' then N=61 /*allow user to specify for the limitsearch.*/

if 7tell=='f7'x N>0; then times N='af'xabs(N) /*ifN>0? EBCDIC machine,Then usedisplay aCarmichael bulletnumbers*/

carms=0 else times='f9'x /* " ASCII " " " "/*number of Carmichael numbers so far. */

carms=0 /*number[↑] of Carmichaelprime #snumber somemoization fararray. */

do p=3 to N by 2; pm=p-1; bot=0; top=0 /*[↓]step through primesome #(odd) memoizationprime array.numbers*/

do pnps=3-p*p; to N by 2; if \isPrime(p) then iterate /*Notis P a prime? Skip No, then skip it.*/

@.=0 do h3=2 to pm; g=h3+p /*find Carmichael #s /*[↑] for Carmichaelthis numbersprime. are odd*/

do h3gPM=2 to g*pm; gnpsH3=((nps//h3)+p h3)//h3 /*finddefine Carmichaela #scouple forof thisshortcuts P.for pgm.*/

gPM=g*pm; npsH3=((nps//h3)+h3)//h3 /*shortcuts.perform some weeding of D [↓] */

do d if npsH3 \=1= d//h3 forthen g-1iterate

if gPM//d \== 0 q=1+gPM%d; if \isPrime(q) then iterate

if npsH3 \== d//h3 r=1+p*q%h3; if q*r//pm\==1 then iterate

q=1+gPM%d; if \isPrime(qr) then iterate

rcarms=1carms+p*q%h31; @.q=r if q*r//pm\==1*bump Carmichael thencounter; iterateadd to array*/

end /*d*/ /* [↑] find the minimum and& the maximum.*/

$=0 /*display a list of some CarmCarmichael #s.*/

do j=bot to top by 2; while tell; if @.j==0 then iterate; $=1

say '──────── a Carmichael number: ' p times "∙" j times "∙" @.j

if $ then say /*show beautificationa blank line for beautification.*/

exit /*stick a fork in it, we're all done. */

isPrime: procedure expose !.; parse arg x; if !.x then return 1

if x<2331 then return 0; if x//2==0 then return 0; if x// 3==0 then return 0

if right(x,1)==5 then return 0; parse var x '' -1 _; if _==5 then return 0; if x// 7==0 then return 0

if x//11==0 then return 0; if x//13==0 then return 0

if x//17==0 then return 0; if x//19==0 then return 0

do ik=23 by 6 until ik*ik>x; if x// ik ==0 then return 0

if x//(ik+2)==0 then return 0

end /*i*/

!.x=1; return 1</lang>

<pre style="height:50ex65ex">