Truncatable primes: Difference between revisions
Content added Content deleted
(→{{header|REXX}}: added comments & whitespace, support for specifying the upper limit, optimized prime number generator. -- ~~~~) |
|||
| Line 1,582: | Line 1,582: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Extra code was added to the prime number generator as this was the part of the REXX program that consumed the vast majority of the time. |
|||
<lang REXX>/*REXX pgm finds largest left- and right-truncatable primes < 1 million.*/ |
<lang REXX>/*REXX pgm finds largest left- and right-truncatable primes < 1 million.*/ |
||
parse arg high .; if high=='' then high=1000000 /*assume 1 million.*/ |
|||
!.=0 |
!.=0; Lp=0; Rp=0 /*placeholders for primes, Lp, Rp*/ |
||
p.1=2; p.2=3; p.3=5; p.4=7; p.5=11; p.6=13; p.7=17 /*some low primes.*/ |
p.1=2; p.2=3; p.3=5; p.4=7; p.5=11; p.6=13; p.7=17 /*some low primes.*/ |
||
!.2=1; !.3=1; !. |
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1 /*low prime flags.*/ |
||
n=7 |
n=7; s.7=17**2 /*number of primes so far. */ |
||
/*───────────────────────────────────────generate primes ≤ high. */ |
|||
| ⚫ | |||
call time 'Reset' |
|||
| ⚫ | |||
if j//3 ==0 then iterate /*divisible by three? */ |
if j//3 ==0 then iterate /*divisible by three? */ |
||
if right(j,1)==5 then iterate /*right-most digit a five? */ |
if right(j,1)==5 then iterate /*right-most digit a five? */ |
||
if j//7 ==0 then iterate /*divisible by seven? */ |
if j//7 ==0 then iterate /*divisible by seven? */ |
||
if j//11 ==0 then iterate /*divisible by eleven? */ |
if j//11 ==0 then iterate /*divisible by eleven? */ |
||
if j//13 ==0 then iterate /*divisible by thirteen? */ |
|||
/*[↑] above five lines saves time*/ |
|||
do k=7 while s.k<=j /*divide by known odd primes. */ |
|||
if j//p.k==0 then iterate j /*Is divisible by X? Not prime.*/ |
if j//p.k==0 then iterate j /*Is divisible by X? Not prime.*/ |
||
end /*k*/ |
end /*k*/ |
||
n=n+1 /*bump number of primes found. */ |
n=n+1 /*bump number of primes found. */ |
||
p.n=j |
p.n=j; s.n=j*j /*assign to sparse array; prime².*/ |
||
!.j=1 /*indicate that J is a prime.*/ |
!.j=1 /*indicate that J is a prime.*/ |
||
end /*j*/ |
end /*j*/ |
||
say 'generation of primes took' format(time('E'),,2) "seconds." |
|||
/*───────────────────────────────────────find largest left truncatable P*/ |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
lp=0; rp=0 |
|||
| ⚫ | |||
do k=1 for length(p.L)-1; _=right(p.L,k) /*truncate a #.*/ |
do k=1 for length(p.L)-1; _=right(p.L,k) /*truncate a #.*/ |
||
if \!._ then iterate L /*Truncated # ¬prime? Skip it.*/ |
if \!._ then iterate L /*Truncated # ¬prime? Skip it.*/ |
||
| Line 1,612: | Line 1,613: | ||
lp=p.L |
lp=p.L |
||
end /*L*/ |
end /*L*/ |
||
/*───────────────────────────────────────find largest right truncatable P*/ |
|||
do R=n by -1 |
do R=n by -1 for n while rp==0; if pos(0,p.R)\==0 then iterate |
||
do k=1 for length(p.R)-1; _=left(p.R,k) /*truncate a #.*/ |
do k=1 for length(p.R)-1; _=left(p.R,k) /*truncate a #.*/ |
||
if \!._ then iterate R /*Truncated # ¬prime? Skip it.*/ |
if \!._ then iterate R /*Truncated # ¬prime? Skip it.*/ |
||
| Line 1,619: | Line 1,620: | ||
rp=p.R |
rp=p.R |
||
end /*R*/ |
end /*R*/ |
||
/*───────────────────────────────────────show largest left/right trunc P*/ |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
/*stick a fork in it, we're done.*/</lang> |
/*stick a fork in it, we're done.*/</lang> |
||
'''output''' |
'''output''' |
||