Truncatable primes: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: changed output to conform to program's output.) |
m (→{{header|REXX}}: changed some comments, optimized the prime generation part of the program.) |
||
| Line 1,640: | Line 1,640: | ||
=={{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 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 time. |
||
<lang REXX>/*REXX pgm finds largest left- |
<lang REXX>/*REXX pgm finds largest left- & right-truncatable primes ≤1m (or arg1).*/ |
||
parse arg high .; if high=='' then high=1000000 |
parse arg high .; if high=='' then high=1000000 /*assume 1 million.*/ |
||
!.=0; Lp=0; Rp=0; w=length(high) /*placeholders for primes, Lp, Rp*/ |
!.=0; Lp=0; Rp=0; w=length(high) /*placeholders for primes, Lp, Rp*/ |
||
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17 /*some low primes. */ |
|||
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1 |
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1 /*low prime flags. */ |
||
#=7; s.#=@.#**2 /*number of primes so far, prime²*/ |
|||
/*───────────────────────────────────────generate more primes ≤ high. */ |
/*───────────────────────────────────────generate more primes ≤ high. */ |
||
do j= |
do j=@.#+2 by 2 to high /*only find odd primes from here.*/ |
||
if j//3 ==0 then iterate /*is J divisible by three? */ |
if j//3 ==0 then iterate /*is J divisible by three? */ |
||
if right(j,1)==5 then iterate /*is the right-most digit a "5" ?*/ |
if right(j,1)==5 then iterate /*is the right-most digit a "5" ?*/ |
||
| Line 1,655: | Line 1,655: | ||
/*[↑] above five lines saves time*/ |
/*[↑] above five lines saves time*/ |
||
do k=7 while s.k<=j /*divide by known odd primes. */ |
do k=7 while s.k<=j /*divide by known odd primes. */ |
||
if j// |
if j//@.k==0 then iterate j /*Is J divisible by X? ¬ prime.*/ |
||
end /*k*/ |
end /*k*/ |
||
#=#+1 /*bump number of primes found. */ |
|||
@.#=j; s.#=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*/ |
||
/*─────────────────────────────────────find largest left truncatable P. */ |
/*─────────────────────────────────────find largest left truncatable P. */ |
||
do L= |
do L=# by -1 for #; if pos(0,@.L)\==0 then iterate |
||
do k=1 for length( |
do k=1 for length(@.L)-1; _=right(@.L,k) /*L truncate #.*/ |
||
if \!._ then iterate L /*Truncated # ¬prime? Skip it.*/ |
if \!._ then iterate L /*Truncated # ¬prime? Skip it.*/ |
||
end /*k*/ |
end /*k*/ |
||
| Line 1,669: | Line 1,669: | ||
end /*L*/ |
end /*L*/ |
||
/*─────────────────────────────────────find largest right truncatable P.*/ |
/*─────────────────────────────────────find largest right truncatable P.*/ |
||
do R= |
do R=# by -1 for #; if pos(0,@.R)\==0 then iterate |
||
do k=1 for length( |
do k=1 for length(@.R)-1; _=left(@.R,k) /*R truncate #.*/ |
||
if \!._ then iterate R /*Truncated # ¬prime? Skip it.*/ |
if \!._ then iterate R /*Truncated # ¬prime? Skip it.*/ |
||
end /*k*/ |
end /*k*/ |
||
| Line 1,676: | Line 1,676: | ||
end /*R*/ |
end /*R*/ |
||
/*───────────────────────────────────────show largest left/right trunc P*/ |
/*───────────────────────────────────────show largest left/right trunc P*/ |
||
say 'The last prime found is ' |
say 'The last prime found is ' @.# " (there are" # 'primes ≤' high")." |
||
say copies('─',70) /*show a separator line. */ |
say copies('─',70) /*show a separator line. */ |
||
say 'The largest left-truncatable prime ≤' high " is " right( |
say 'The largest left-truncatable prime ≤' high " is " right(@.L,w) |
||
say 'The largest right-truncatable prime ≤' high " is " right( |
say 'The largest right-truncatable prime ≤' high " is " right(@.R,w) |
||
/*stick a fork in it, we're done.*/</lang> |
/*stick a fork in it, we're done.*/</lang> |
||
'''output''' |
'''output''' |
||