Anonymous user
Carmichael 3 strong pseudoprimes: Difference between revisions
→{{header|REXX}}: added the REXX language. -- ~~~~
No edit summary |
(→{{header|REXX}}: added the REXX language. -- ~~~~) |
||
Line 22:
Related Tasks:
:[http://rosettacode.org/wiki/Miller-Rabin_primality_test Miller-Rabin primality test]
=={{header|REXX}}==
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).
<lang rexx>/*REXX program calculates Carmichael 3-strong pseudoprimes. */
numeric digits 30 /*in case user wants bigger nums.*/
parse arg h .; if h=='' then h=61 /*allow user to specify the limit*/
if 1=='f1'x then times='af'x /*if EBCDIC machine, use a bullet*/
else times='f9'x /* " ASCII " " " " */
carms=0 /*number of Carmichael #s so far.*/
!.=0 /*a method of prime memoization. */
do j=1 to h by 2; p=j; if p==1 then p=2
if \isPrime(p) then iterate /*Not prime? Then keep truckin'.*/
pm=p-1 /*use this for "prime less one." */
nps=-p*p /*another handy-dandy variable. */
do h3=2 to pm; g=h3+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) | q==p then iterate
r=1+p*q%h3; if \isPrime(r) | q*r//pm\==1 then iterate
say '──────── a Carmichael number: ' p times q times r
carms=carms+1 /*bump the Carmichael # counter. */
end /*d*/
end /*h3*/
say /*show bueatification blank line.*/
end /*j*/
say; say carms ' Carmichael numbers found.'
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────ISPRIME subroutine──────────────────*/
isPrime: procedure expose !.; parse arg x; if !.x then return 1
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
do i=5 by 6 until i*i>x; if x//i==0 then return 0
if x//(i+2)==0 then return 0
end /*i*/
!.x=1
return 1</lang>
'''output''' when using the default input
<pre style="height:30ex;overflow:scroll">
──────── a Carmichael number: 3 ∙ 11 ∙ 17
──────── a Carmichael number: 5 ∙ 29 ∙ 73
──────── a Carmichael number: 5 ∙ 17 ∙ 29
──────── a Carmichael number: 5 ∙ 13 ∙ 17
──────── a Carmichael number: 7 ∙ 19 ∙ 67
──────── a Carmichael number: 7 ∙ 31 ∙ 73
──────── a Carmichael number: 7 ∙ 13 ∙ 31
──────── a Carmichael number: 7 ∙ 23 ∙ 41
──────── a Carmichael number: 7 ∙ 73 ∙ 103
──────── a Carmichael number: 7 ∙ 13 ∙ 19
──────── a Carmichael number: 13 ∙ 61 ∙ 397
──────── a Carmichael number: 13 ∙ 37 ∙ 241
──────── a Carmichael number: 13 ∙ 97 ∙ 421
──────── a Carmichael number: 13 ∙ 37 ∙ 97
──────── a Carmichael number: 13 ∙ 37 ∙ 61
──────── a Carmichael number: 17 ∙ 41 ∙ 233
──────── a Carmichael number: 17 ∙ 353 ∙ 1201
──────── a Carmichael number: 19 ∙ 43 ∙ 409
──────── a Carmichael number: 19 ∙ 199 ∙ 271
──────── a Carmichael number: 23 ∙ 199 ∙ 353
──────── a Carmichael number: 29 ∙ 113 ∙ 1093
──────── a Carmichael number: 29 ∙ 197 ∙ 953
──────── a Carmichael number: 31 ∙ 991 ∙ 15361
──────── a Carmichael number: 31 ∙ 61 ∙ 631
──────── a Carmichael number: 31 ∙ 151 ∙ 1171
──────── a Carmichael number: 31 ∙ 61 ∙ 271
──────── a Carmichael number: 31 ∙ 61 ∙ 211
──────── a Carmichael number: 31 ∙ 271 ∙ 601
──────── a Carmichael number: 31 ∙ 181 ∙ 331
──────── a Carmichael number: 37 ∙ 109 ∙ 2017
──────── a Carmichael number: 37 ∙ 73 ∙ 541
──────── a Carmichael number: 37 ∙ 613 ∙ 1621
──────── a Carmichael number: 37 ∙ 73 ∙ 181
──────── a Carmichael number: 37 ∙ 73 ∙ 109
──────── a Carmichael number: 41 ∙ 1721 ∙ 35281
──────── a Carmichael number: 41 ∙ 881 ∙ 12041
──────── a Carmichael number: 41 ∙ 101 ∙ 461
──────── a Carmichael number: 41 ∙ 241 ∙ 761
──────── a Carmichael number: 41 ∙ 241 ∙ 521
──────── a Carmichael number: 41 ∙ 73 ∙ 137
──────── a Carmichael number: 41 ∙ 61 ∙ 101
──────── a Carmichael number: 43 ∙ 631 ∙ 13567
──────── a Carmichael number: 43 ∙ 271 ∙ 5827
──────── a Carmichael number: 43 ∙ 127 ∙ 2731
──────── a Carmichael number: 43 ∙ 127 ∙ 1093
──────── a Carmichael number: 43 ∙ 211 ∙ 757
──────── a Carmichael number: 43 ∙ 631 ∙ 1597
──────── a Carmichael number: 43 ∙ 127 ∙ 211
──────── a Carmichael number: 43 ∙ 211 ∙ 337
──────── a Carmichael number: 43 ∙ 433 ∙ 643
──────── a Carmichael number: 43 ∙ 547 ∙ 673
──────── a Carmichael number: 43 ∙ 3361 ∙ 3907
──────── a Carmichael number: 47 ∙ 3359 ∙ 6073
──────── a Carmichael number: 47 ∙ 1151 ∙ 1933
──────── a Carmichael number: 47 ∙ 3727 ∙ 5153
──────── a Carmichael number: 53 ∙ 157 ∙ 2081
──────── a Carmichael number: 53 ∙ 79 ∙ 599
──────── a Carmichael number: 53 ∙ 157 ∙ 521
──────── a Carmichael number: 59 ∙ 1451 ∙ 2089
──────── a Carmichael number: 61 ∙ 421 ∙ 12841
──────── a Carmichael number: 61 ∙ 181 ∙ 5521
──────── a Carmichael number: 61 ∙ 1301 ∙ 19841
──────── a Carmichael number: 61 ∙ 277 ∙ 2113
──────── a Carmichael number: 61 ∙ 181 ∙ 1381
──────── a Carmichael number: 61 ∙ 541 ∙ 3001
──────── a Carmichael number: 61 ∙ 661 ∙ 2521
──────── a Carmichael number: 61 ∙ 271 ∙ 571
──────── a Carmichael number: 61 ∙ 241 ∙ 421
──────── a Carmichael number: 61 ∙ 3361 ∙ 4021
69 Carmichael numbers found.
</pre>
=={{header|Ruby}}==
| |||