Carmichael 3 strong pseudoprimes: Difference between revisions

← Older editNewer edit →
Content deleted Content added
m →‎{{header|REXX}}: made some cometic changes, removed calculation with even prime (Carmicahael numbers can't be even). -- ~~~~
Line 283: Line 283:
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes. */
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes. */
numeric digits 30 /*in case user wants bigger nums.*/
numeric digits 30 /*in case user wants bigger nums.*/
parse arg h .; if h=='' then h=61 /*allow user to specify the limit*/
parse arg N .; if N=='' then N=61 /*allow user to specify the limit*/
if 1=='f1'x then times='af'x /*if EBCDIC machine, use a bullet*/
if 1=='f1'x then times='af'x /*if EBCDIC machine, use a bullet*/
else times='f9'x /* " ASCII " " " " */
else times='f9'x /* " ASCII " " " " */
carms=0 /*number of Carmichael #s so far.*/
carms=0 /*number of Carmichael #s so far.*/
!.=0 /*a method of prime memoization. */
!.=0 /*a method of prime memoization. */
do p=3 to N by 2; if \isPrime(p) then iterate /*Not prime? Skip.*/

do j=1 to h by 2; p=j; if p==1 then p=2
pm=p-1; nps=-p*p /*couple of handy-dandy variables*/
if \isPrime(p) then iterate /*Not prime? Then keep truckin'.*/
do h3=2 to pm; g=h3+p /*find Carmichael #s for this P. */
pm=p-1 /*use this for "prime less one." */
do d=1 to g-1
nps=-p*p /*another handy-dandy variable. */
if g*pm//d\==0 | ((nps//h3)+h3)//h3\==d//h3 then iterate
q=1+pm*g%d; if \isPrime(q) | q==p then iterate

do h3=2 to pm; g=h3+p
r=1+p*q%h3; if \isPrime(r) | q*r//pm\==1 then iterate
say '──────── a Carmichael number: ' p times q times r
do d=1 to g-1
carms=carms+1 /*bump the Carmichael # counter. */
if g*pm//d\==0 | ((nps//h3)+h3)//h3\==d//h3 then iterate
q=1+pm*g%d; if \isPrime(q) | q==p then iterate
end /*d*/
r=1+p*q%h3; if \isPrime(r) | q*r//pm\==1 then iterate
end /*h3*/
say '──────── a Carmichael number: ' p times q times r
say /*show bueatification blank line.*/
carms=carms+1 /*bump the Carmichael # counter. */
end /*p*/
end /*d*/
end /*h3*/
say /*show bueatification blank line.*/
end /*j*/

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 done.*/
Line 312: Line 307:
if wordpos(x,'2 3 5 7')\==0 then do; !.x=1; return 1; end
if wordpos(x,'2 3 5 7')\==0 then do; !.x=1; return 1; end
if x<11 then return 0; if x//2==0 then return 0; if x//3==0 then return 0
if x<11 then return 0; if x//2==0 then return 0; if x//3==0 then return 0
⚫
do i=5 by 6 until i*i>x; if x// i ==0 then return 0

do i=5 by 6 until i*i>x; if x//i==0 then return 0
if x//(i+2) ==0 then return 0
⚫
if x//(i+2)==0 then return 0
end /*i*/
end /*i*/
!.x=1
!.x=1; return 1</lang>
return 1</lang>
'''output''' when using the default input
'''output''' when using the default input
<pre style="height:30ex;overflow:scroll">
<pre style="height:30ex;overflow:scroll">
Retrieved from "https://rosettacode.org/wiki/Carmichael_3_strong_pseudoprimes"