Substring primes: Difference between revisions
(→{{header|REXX}}: added the computer programming language REXX.) |
(Added Algol 68) |
||
Line 5: | Line 5: | ||
Primes (in base ten) in which all substrings are also primes, where '''n < 500''' |
Primes (in base ten) in which all substrings are also primes, where '''n < 500''' |
||
<br><br> |
<br><br> |
||
=={{header|ALGOL 68}}== |
|||
<lang algol68>BEGIN # find primes where all substrings of the digits are prime # |
|||
# reurns a sieve of primes up to n # |
|||
PROC sieve = ( INT n )[]BOOL: |
|||
BEGIN |
|||
[ 1 : n ]BOOL p; |
|||
p[ 1 ] := FALSE; p[ 2 ] := TRUE; |
|||
FOR i FROM 3 BY 2 TO n DO p[ i ] := TRUE OD; |
|||
FOR i FROM 4 BY 2 TO n DO p[ i ] := FALSE OD; |
|||
FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO |
|||
IF p[ i ] THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := FALSE OD FI |
|||
OD; |
|||
p |
|||
END # prime list # ; |
|||
# find the primes of interest # |
|||
INT max number = 500; |
|||
[]BOOL prime = sieve( max number ); |
|||
FOR p TO UPB prime DO |
|||
IF prime[ p ] THEN |
|||
INT d := 10; |
|||
BOOL is substring := TRUE; |
|||
WHILE is substring AND d <= max number DO |
|||
INT n := p; |
|||
WHILE is substring AND n > 0 DO |
|||
INT sub digits = n MOD d; |
|||
is substring := IF sub digits = 0 THEN FALSE ELSE prime[ sub digits ] FI; |
|||
n OVERAB 10 |
|||
OD; |
|||
d *:= 10 |
|||
OD; |
|||
IF is substring THEN print( ( " ", whole( p, 0 ) ) ) FI |
|||
FI |
|||
OD |
|||
END</lang> |
|||
{{out}} |
|||
<pre> |
|||
2 3 5 7 23 37 53 73 373 |
|||
</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
Revision as of 17:11, 5 April 2021
- Task
Primes (in base ten) in which all substrings are also primes, where n < 500
ALGOL 68
<lang algol68>BEGIN # find primes where all substrings of the digits are prime #
# reurns a sieve of primes up to n # PROC sieve = ( INT n )[]BOOL: BEGIN [ 1 : n ]BOOL p; p[ 1 ] := FALSE; p[ 2 ] := TRUE; FOR i FROM 3 BY 2 TO n DO p[ i ] := TRUE OD; FOR i FROM 4 BY 2 TO n DO p[ i ] := FALSE OD; FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO IF p[ i ] THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := FALSE OD FI OD; p END # prime list # ; # find the primes of interest # INT max number = 500; []BOOL prime = sieve( max number ); FOR p TO UPB prime DO IF prime[ p ] THEN INT d := 10; BOOL is substring := TRUE; WHILE is substring AND d <= max number DO INT n := p; WHILE is substring AND n > 0 DO INT sub digits = n MOD d; is substring := IF sub digits = 0 THEN FALSE ELSE prime[ sub digits ] FI; n OVERAB 10 OD; d *:= 10 OD; IF is substring THEN print( ( " ", whole( p, 0 ) ) ) FI FI OD
END</lang>
- Output:
2 3 5 7 23 37 53 73 373
REXX
<lang rexx>/*REXX program finds/shows decimal primes where all substrings are also prime, N < 500.*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 500 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 7 /*width of a number in any column. */
@sprs= ' primes (base ten) where all substrings are also primes < ' hi
say ' index │'center(@sprs, 1 + cols*(w+1) ) /*display the title of the output. */ say '───────┼'center("" , 1 + cols*(w+1), '─') /* " " separator " " " */ $= /*a list of substring primes (so far). */
do j=1 for #; x= @.j; x2= substr(x, 2) /*search for primes that fit criteria. */ if verify(x, 014689, 'M')>0 then iterate /*does X prime have any of these digs?*/ if verify(x2, 25 , 'M')>0 then iterate /* " X2 part " " " " " */ L= length(x) /*obtain the length of the X prime.*/ do k=1 for L-1 /*test for primality for all substrings*/ do m=k+1 to L; y= substr(x, k, m-1) /*extract a substring from the X prime.*/ if \!.y then iterate j /*does substring of X not prime? Skip.*/ end /*m*/ end /*k*/
$= $ right(x, w) /*add the X prime to the $ list. */ end /*j*/
if $\== then say center(1,7)"│" substr($, 2) /*display the list of substring primes.*/ say say 'Found ' words($) @sprs exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0 /*placeholders for primes (semaphores).*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ #=5; s.#= @.# **2 /*number of primes so far; prime². */ /* [↓] generate more primes ≤ high.*/ do j=@.#+2 by 2 to hi /*find odd primes from here on. */ parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ if j// 7==0 then iterate /*" " " 7? */ /* [↑] the above 3 lines saves time.*/ 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. ___ */ end /*k*/ /* [↑] only process numbers ≤ √ J */ #= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default inputs:
index │ primes (base ten) where all substrings are also primes < 500 ───────┼───────────────────────────────────────────────────────────────────────────────── 1 │ 2 3 5 7 23 37 53 73 373 Found 9 primes (base ten) where all substrings are also primes < 500
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "Numbers in which all substrings are primes:" + nl
row = 0 limit1 = 500
for n = 1 to limit1
flag = 1 strn = string(n) for m = 1 to len(strn) for p = 1 to len(strn) temp = substr(strn,m,p) if temp != "" if isprime(number(temp)) flag = 1 else flag = 0 exit 2 ok ok next next if flag = 1 see "" + n + " " ok
next
see nl + "Found " + row + " numbers in which all substrings are primes" + nl see "done..." + nl </lang>
- Output:
working... Numbers in which all substrings are primes: 2 3 5 7 23 37 53 73 373 Found 9 numbers in which all substrings are primes done...