Truncatable primes: Difference between revisions
Content deleted Content added
Added Uiua solution |
Walterpachl (talk | contribs) →{{header|REXX}}: improve readability (vastly) and ooRexx compatible |
||
| Line 3,221: | Line 3,221: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Extra code was added to the prime number generator as this is the section of the REXX program that consumes the vast majority of the computation time. |
Extra code was added to the prime number generator as this is the section of the REXX program that consumes the vast majority of the computation time. |
||
<syntaxhighlight lang="rexx">/*REXX program finds largest |
<syntaxhighlight lang="rexx">/*REXX program finds largest left- and right-truncatable primes less than hi */ |
||
Parse Arg hi . |
|||
parse arg hi .; if hi=='' then hi= 1000000 /*Not specified? Then use default of 1m*/ |
|||
If hi=='' Then |
|||
call genP /*generate some primes, about hi ÷ 2 */ |
|||
hi=1000000 /* Not specified? Then use default */ |
|||
Call genP /* generate primes up to hi */ |
|||
do k=1 for length(@.L); _= right(@.L, k) /*validate all left truncatable primes.*/ |
|||
if \!._ then iterate L /*Truncated number not prime? Skip it.*/ |
|||
end /*k*/ |
|||
leave /*egress, found left truncatable prime.*/ |
|||
end /*L*/ |
|||
/* [↓] find largest right truncated P.*/ |
|||
do R=# by -1 for # /*search from top end; get the length.*/ |
|||
do k=1 for length(@.R); _= left(@.R, k) /*validate all right truncatable primes*/ |
|||
if \!._ then iterate R /*Truncated number not prime? Skip it.*/ |
|||
end /*k*/ |
|||
leave /*egress, found right truncatable prime*/ |
|||
end /*R*/ |
|||
/* find largest left truncatable Prime */ |
|||
say 'The largest left─truncatable prime ≤' hi " is " right(@.L, w) |
|||
Do l=prime.0 By -1 /* search from top end; */ |
|||
left.0=length(prime.l) |
|||
exit /*stick a fork in it, we're all done. */ |
|||
Do k=1 For length(prime.l) |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
_=right(prime.l,k) /* validate left truncatable ptime */ |
|||
left.k=_ |
|||
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ |
|||
If \is_prime._ Then |
|||
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ |
|||
Iterate l /* Truncated number not prime? Skip */ |
|||
End |
|||
/* [↓] generate more primes ≤ high.*/ |
|||
Leave |
|||
do j=@.#+2 by 2 for max(0, hi%2-@.#%2-1) /*find odd primes from here on. */ |
|||
End |
|||
parse var j '' -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ |
|||
if j// 3==0 then iterate /*" " " 3? */ |
|||
/* find largest right truncated Prime */ |
|||
if j// 7==0 then iterate /*" " " 7? */ |
|||
Do r=prime.0 By -1 /* search from top end; */ |
|||
right.0=length(prime.r) |
|||
do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/ |
|||
Do k=1 For length(prime.r) |
|||
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ |
|||
_=left(prime.r,k) |
|||
end /*k*/ /* [↑] only process numbers ≤ √ J */ |
|||
right.k=_ |
|||
#= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ |
|||
If \is_prime._ Then |
|||
end /*j*/ |
|||
Iterate r /* Truncated number not prime? Skip */ |
|||
return</syntaxhighlight> |
|||
End |
|||
Leave |
|||
End |
|||
Say 'The largest left-truncatable prime smaller than' hi 'is' prime.l |
|||
do i=left.0-1 to 1 By -1 |
|||
say right(left.i,66) |
|||
End |
|||
Say 'The largest right-truncatable prime smaller than' hi 'is' prime.r |
|||
do i=right.0-1 to 1 By -1 |
|||
say copies(' ',60)right.i |
|||
End |
|||
Exit /* stick a fork in it, we're all done */ |
|||
/*-----------------------------------------------------------------------------*/ |
|||
genp: |
|||
Call time 'R' |
|||
Call init 2 3 5 7 11 13 17 19 |
|||
Do j=21 to hi By 2 |
|||
Select |
|||
When right(j,1)=5 Then Iterate |
|||
When j//3==0 Then Iterate |
|||
When j//7==0 Then Iterate |
|||
Otherwise Nop |
|||
End |
|||
Do k=5 While s.k<=j |
|||
If j//prime.k==0 Then |
|||
Iterate j |
|||
End |
|||
Call store j /* j is prime */ |
|||
End |
|||
Say prime.0 'primes smaller than' hi '--' time('E') 'seconds' |
|||
Return |
|||
init: |
|||
Parse Arg plist |
|||
is_prime.=0 |
|||
prime.=0 |
|||
Do i=1 To words(plist) |
|||
Call store word(plist,i) |
|||
End |
|||
Return |
|||
store: |
|||
Parse Arg p |
|||
z=prime.0+1 |
|||
prime.z=p |
|||
s.z=p*p |
|||
prime.0=z |
|||
is_prime.p=1 |
|||
Return</syntaxhighlight> |
|||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
78498 primes smaller than 1000000 -- 8.763000 seconds |
|||
The largest left─truncatable prime ≤ 1000000 is 998443 |
|||
The largest |
The largest left-truncatable prime smaller than 1000000 is 998443 |
||
98443 |
|||
8443 |
|||
443 |
|||
43 |
|||
3 |
|||
The largest right-truncatable prime smaller than 1000000 is 739399 |
|||
73939 |
|||
7393 |
|||
739 |
|||
73 |
|||
7 |
|||
</pre> |
</pre> |
||