Substring primes: Difference between revisions
Content added Content deleted
(Added C++ solution) |
m (Moved C++ entry after Algol 68) |
||
Line 5:
Primes (in base ten) in which all substrings are also primes, where '''n < 500'''
<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|C++}}==
Line 64 ⟶ 103:
73
373
▲</pre>
▲=={{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>
|