Truncatable primes: Difference between revisions

Content added Content deleted
(Rewrite Pike code to be simpler and faster)
m (→‎{{header|REXX}}: simplified the code, added/changed whitespace and comments, used a template for the output section.)
Line 2,628: Line 2,628:
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.
<lang REXX>/*REXX program finds largest left─ and right─truncatable primes ≤ 1m (or argument 1).*/
<lang REXX>/*REXX program finds largest left─ and right─truncatable primes ≤ 1m (or argument 1).*/
parse arg high .; if high=='' then high=1000000 /*Not specified? Then use 1m*/
parse arg HI .; if HI=='' then HI= 1000000 /*Not specified? Then use default of 1m*/
!.=0; w=length(high) /*placeholders for primes; max width. */
!.= 0; w= length(HI) /*placeholders for primes; max width. */
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17 /*define some low primes. */
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1 /*set some low prime flags. */
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */
#=7; s.#=@.#**2 /*number of primes so far; prime². */
#=5; s.#= @.# **2 /*number of primes so far; prime². */
/* [↓] generate more primes ≤ high.*/
/* [↓] generate more primes ≤ high.*/
do j=@.#+2 by 2 for max(0, high%2-@.#%2-1) /*only find odd primes from here on out*/
do j=@.#+2 by 2 for max(0, HI%2 - @.#%2 - 1) /*only find odd primes from here on out*/
if j// 3==0 then iterate /*is J divisible by three? */
if j// 3==0 then iterate /*is J divisible by three? */
parse var j '' -1 _; if _==5 then iterate /* " " " " five? (right digit)*/
parse var j '' -1 _; if _==5 then iterate /* " " " " five? (right digit)*/
if j// 7==0 then iterate /* " " " " seven? */
if j// 7==0 then iterate /* " " " " seven? */
if j//11==0 then iterate /* " " " " eleven? */
if j//13==0 then iterate /* " " " " thirteen? */
/* [↑] the above five lines saves time*/
/* [↑] the above five lines saves time*/
do k=7 while s.k<=j /* [↓] divide by the known odd primes.*/
do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/
if j//@.k==0 then iterate j /*Is J ÷ X? Then not prime. ___ */
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process up to the √ J */
end /*k*/ /* [↑] only process numers ≤ √ J */
#=#+1 /*bump the number of primes found. */
#= #+1 /*bump the number of primes found. */
@.#=j; s.#=j*j; !.j=1 /*assign next prime; prime²; prime #.*/
@.#= j; s.#= j * j; !.j= 1 /*assign next prime; prime²; prime #.*/
end /*j*/
end /*j*/
/* [↓] find largest left truncatable P*/
/* [↓] find largest left truncatable P*/
do L=# by -1 for #; digs=length(@.L) /*search from top end; get the length.*/
do L=# by -1 for # /*search from top end; get the length.*/
do k=1 for digs; _=right(@.L, k) /*validate all left truncatable primes.*/
do k=1 for length(@.L); _=right(@.L, k) /*validate all left truncatable primes.*/
if \!._ then iterate L /*Truncated number not prime? Skip it.*/
if \!._ then iterate L /*Truncated number not prime? Skip it.*/
end /*k*/
end /*k*/
leave /*egress, found left truncatable prime.*/
leave /*egress, found left truncatable prime.*/
end /*L*/
end /*L*/
/* [↓] find largest right truncated P.*/
/* [↓] find largest right truncated P.*/
do R=# by -1 for #; digs=length(@.R) /*search from top end; get the length.*/
do R=# by -1 for # /*search from top end; get the length.*/
do k=1 for digs; _=left(@.R, k) /*validate all right truncatable primes*/
do k=1 for length(@.R); _= left(@.R, k) /*validate all right truncatable primes*/
if \!._ then iterate R /*Truncated number not prime? Skip it.*/
if \!._ then iterate R /*Truncated number not prime? Skip it.*/
end /*k*/
end /*k*/
leave /*egress, found right truncatable prime*/
leave /*egress, found right truncatable prime*/
end /*R*/
end /*R*/
/* [↓] show largest left/right trunc P*/
/*stick a fork in it, we're all done. */
say 'The last prime found is ' @.# " (there are" # 'primes ≤' high")."
say 'The largest left─truncatable prime ≤' HI " is " right(@.L, w)
say copies('─', 70) /*show a separator line for the output.*/
say 'The largest right─truncatable prime ≤' HI " is " right(@.R, w)</lang>
⚫
{{out|output|text=&nbsp; when using the default inputs:}}
say 'The largest left─truncatable prime ≤' high " is " right(@.L, w)
say 'The largest right─truncatable prime ≤' high " is " right(@.R, w)
/*stick a fork in it, we're all done. */</lang>
⚫
'''output''' &nbsp; when using the default input:
<pre>
<pre>
The last prime found is 999983 (there are 78498 primes ≤ 1000000).
──────────────────────────────────────────────────────────────────────
The largest left─truncatable prime ≤ 1000000 is 998443
The largest left─truncatable prime ≤ 1000000 is 998443
The largest right─truncatable prime ≤ 1000000 is 739399
The largest right─truncatable prime ≤ 1000000 is 739399
Retrieved from "https://rosettacode.org/wiki/Truncatable_primes"