Carmichael 3 strong pseudoprimes: Difference between revisions

← Older editNewer edit →
Content deleted Content added
m →‎numbers in order of calculation: optimized code. -- ~~~~
m →‎{{header|REXX}}: optimized the '''IF''' statements by unrolling them. -- ~~~~
Line 277:
 
=={{header|REXX}}==
<br><br>Note that REXX's version of '''modulus''' ('''//''') is really a ''remainder'' function, so a version of▼
The REXX '''if''' statements could be optimized within the '''do h3''' loop by unrolling them, and
<br>also by implementing a faster '''isPrime''' function.
▲<br><br>Note that REXX's version of '''modulus''' ('''//''') is really a ''remainder'' function, so a version of
<br>the '''modulus''' function was hard-coded below (when using a negative value).
===numbers in order of calculation===
Line 425 ⟶ 423:
 
do h3=2 to pm; g=h3+p /*find Carmichael #s for this P. */
 
do d=1 to g-1
if g*pm//d\==0 | ((nps//h3)+h3)//h3\==d//h3 then iterate
q=1+pm*g%d; if \isPrime(q(nps//h3) | q+h3)//h3\==p d//h3 then iterate
rq=1+ppm*qg%h3d; if \isPrime(rq) | q*r//pm\==1 then iterate
r=1+p*q%h3; if q*r//pm\==1 then iterate
if \isPrime(r) then iterate
carms=carms+1 /*bump the Carmichael # counter. */
min=min(min,q); max=max(max,q); @.q=r /*build a list.*/
end /*d*/
 
end /*h3*/
/*display a list of some Carm #s.*/
do j=min to max by 2; if @.j==0 then iterate /*one of the #s?*/
say '──────── a Carmichael number: ' p times j times @.j
end /*j*/
Line 446 ⟶ 444:
/*──────────────────────────────────ISPRIME subroutine──────────────────*/
isPrime: procedure expose !.; parse arg x; if !.x then return 1
if wordpos(x,'2 3 5 7 11 13')\==0 then do; !.x=1; return 1; end
if x<1117 then return 0; if x//2==0 then return 0; if x//3==0 then return 0
if do iright(x,1)==5 then byreturn 6 until i*i>x0; if x// i 7==0 then return 0
do i=11 by 6 until i*i>x; if x// i ==0 then return 0
if x//(i+2) ==0 then return 0
end /*i*/
Retrieved from "https://rosettacode.org/wiki/Carmichael_3_strong_pseudoprimes"