Carmichael 3 strong pseudoprimes: Difference between revisions

Content added Content deleted
(Add rust solution)
(→‎{{header|REXX}}: changed/added comments and indentations, optimized some code.)
Line 1,066: Line 1,066:


<br>The Carmichael numbers are shown in numerical order.
<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.
<br>Some code optimization was done, while not necessary for the small default number ('''61'''), &nbsp; it was significant for larger numbers.
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes (up to N).*/
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes (up to and including N). */
numeric digits 30 /*in case user wants bigger nums.*/
numeric digits 30 /*handle big dig #s (9 is the default).*/
parse arg N .; if N=='' then N=61 /*allow user to specify the limit*/
parse arg N .; if N=='' then N=61 /*allow user to specify for the search.*/
if 7=='f7'x then times='af'x /*if EBCDIC machine, use a bullet*/
tell= N>0; N=abs(N) /*N>0? Then display Carmichael numbers*/
else times='f9'x /* " ASCII " " " " */
carms=0 /*number of Carmichael numbers so far. */
⚫
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1; !.23=1; !.29=1; !.31=1
carms=0 /*number of Carmichael #s so far.*/
/*[↑] prime number memoization array. */
⚫
!.=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; pm=p-1; bot=0; top=0 /*step through some (odd) prime numbers*/
do p=3 to N by 2; if \isPrime(p) then iterate /*Not prime? Skip*/
nps=-p*p; if \isPrime(p) then iterate /*is P a prime? No, then skip it.*/
@.=0
pm=p-1; nps=-p*p; bot=0; top=0 /*some handy-dandy REXX variables*/
@.=0 /*[↑] Carmichael numbers are odd*/
do h3=2 to pm; g=h3+p /*find Carmichael #s for this prime. */
do h3=2 to pm; g=h3+p /*find Carmichael #s for this P. */
gPM=g*pm; npsH3=((nps//h3)+h3)//h3 /*define a couple of shortcuts for pgm.*/
gPM=g*pm; npsH3=((nps//h3)+h3)//h3 /*shortcuts.*/
/*perform some weeding of D [↓] */
⚫
do d=1 for g-1; if gPM//d \== 0 then iterate

do d=1 for g-1
if npsH3 \== d//h3 then iterate
if gPM//d \== 0 then iterate
q=1+gPM%d; if \isPrime(q) then iterate
if npsH3 \== d//h3 then iterate
r=1+p*q%h3; if q*r//pm\==1 then iterate
q=1+gPM%d; if \isPrime(q) then iterate
if \isPrime(r) then iterate
r=1+p*q%h3; if q*r//pm\==1 then iterate
carms=carms+1; @.q=r /*bump Carmichael counter; add to array*/
⚫
if \isPrime(r) then iterate
carms=carms+1; @.q=r /*bump Carmichael #; add to array*/
if bot==0 then bot=q; bot=min(bot,q); top=max(top,q)
if bot==0 then bot=q; bot=min(bot,q); top=max(top,q)
end /*d*/ /* [↑] find minimum and maximum.*/
end /*d*/ /* [↑] find the minimum & the maximum.*/
end /*h3*/
end /*h3*/
$=0 /*display a list of some Carm #s.*/
$=0 /*display a list of some Carmichael #s.*/
do j=bot to top by 2; if @.j==0 then iterate; $=1
do j=bot to top by 2 while tell; if @.j==0 then iterate; $=1
say '──────── a Carmichael number: ' p times j times @.j
say '──────── a Carmichael number: ' p "∙" j "∙" @.j
end /*j*/
end /*j*/
if $ then say /*show beautification blank line.*/
if $ then say /*show a blank line for beautification.*/
end /*p*/
end /*p*/


say; say carms ' Carmichael numbers found.'
say; say carms ' Carmichael numbers found.'
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────ISPRIME subroutine──────────────────*/
isPrime: procedure expose !.; parse arg x; if !.x then return 1
isPrime: procedure expose !.; parse arg x; if !.x then return 1
if x<23 then return 0; if x//2==0 then return 0; if x// 3==0 then return 0
if x<31 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; if x// 7==0 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//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
if x//17==0 then return 0; if x//19==0 then return 0
do i=23 by 6 until i*i>x; if x// i ==0 then return 0
do k=23 by 6 until k*k>x; if x// k ==0 then return 0
if x//(i+2)==0 then return 0
if x//(k+2)==0 then return 0
end /*i*/
end /*i*/
!.x=1; return 1</lang>
!.x=1; return 1</lang>
'''output''' &nbsp; when using the default input:
'''output''' &nbsp; when using the default input:
<pre style="height:50ex">
<pre style="height:65ex">
──────── a Carmichael number: 3 ∙ 11 ∙ 17
──────── a Carmichael number: 3 ∙ 11 ∙ 17


Line 1,182: Line 1,180:
──────── a Carmichael number: 61 ∙ 1301 ∙ 19841
──────── a Carmichael number: 61 ∙ 1301 ∙ 19841
──────── a Carmichael number: 61 ∙ 3361 ∙ 4021
──────── a Carmichael number: 61 ∙ 3361 ∙ 4021



69 Carmichael numbers found.
69 Carmichael numbers found.
</pre>
'''output''' &nbsp; when using the input of: &nbsp; <tt> -1000 </tt>
<pre>
1038 Carmichael numbers found.
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Carmichael_3_strong_pseudoprimes"