Prime triangle: Difference between revisions

Content added Content deleted
(→‎{{header|Go}}: Updated in line with Phix example of which this is a translation.)
(→‎{{header|ALGOL 68}}: Slight simplification)
Line 20: Line 20:
FI
FI
OD;
OD;
[ 1 : max number, 1 : max number ]BOOL prime pair;
FOR a TO max number DO
⚫
prime pair[ a, 1 ] := FALSE;
FOR b FROM 2 TO max number DO
⚫
prime pair[ a, b ] := prime[ a + b ]
⚫
OD;
prime pair[ a, a ] := FALSE
OD;
# finds the next number that can follow i or 0 if there isn't one #
PROC find next = ( INT i, INT n, INT current, []BOOL used )INT:
BEGIN
⚫
# the numbers must alternate between even and odd in order for the sum to be prime #
⚫
INT result := IF current > 0 THEN current + 2
⚫
ELIF ODD i THEN 2
⚫
ELSE 3
⚫
FI;
⚫
WHILE IF result >= n THEN FALSE ELSE NOT prime pair[ i, result ] OR used[ result ] FI DO
⚫
result +:= 2
⚫
OD;
⚫
IF result >= n THEN 0 ELSE result FI
⚫
END # find next # ;
# returns the number of possible arrangements of the integers for a row in the prime triangle #
# returns the number of possible arrangements of the integers for a row in the prime triangle #
PROC count arrangements = ( INT n, BOOL print solution )INT:
PROC count arrangements = ( INT n )INT:
IF n < 2 THEN # no solutions for n < 2 # 0
IF n < 2 THEN # no solutions for n < 2 # 0
ELIF n < 4 THEN
ELIF n < 4 THEN
# for 2 and 3. there is only 1 solution: 1, 2 and 1, 2, 3 #
# for 2 and 3. there is only 1 solution: 1, 2 and 1, 2, 3 #
IF print solution THEN
FOR i TO n DO print( ( whole( i, -3 ) ) ) OD; print( ( newline ) );
⚫
FOR i TO n DO print( ( whole( i, -3 ) ) ) OD; print( ( newline ) )
⚫
FI;
1
1
ELSE
ELSE
# 4 or more - must find the solutions #
# 4 or more - must find the solutions #
⚫
BOOL print solution := TRUE;
[ 0 : n ]BOOL used;
[ 0 : n ]BOOL used;
[ 0 : n ]INT number;
[ 0 : n ]INT number;
⚫
# the triangle row must have 1 in the leftmost and n in the rightmost elements #
⚫
# the numbers must alternate between even and odd in order for the sum to be prime #
FOR i FROM 0 TO n DO
FOR i FROM 0 TO n DO
used[ i ] := FALSE;
used[ i ] := FALSE;
number[ i ] := 0
number[ i ] := i MOD 2
OD;
OD;
⚫
used[ 1 ] := TRUE;
⚫
# the triangle row must have 1 in the leftmost and n in the rightmost elements #
number[ 1 ] := 1; used[ 1 ] := TRUE;
number[ n ] := n;
number[ n ] := n; used[ n ] := TRUE;
used[ n ] := TRUE;
# find the intervening numbers and count the solutions #
# find the intervening numbers and count the solutions #
INT count := 0;
INT count := 0;
INT p := 2;
INT p := 2;
WHILE p < n DO
WHILE p > 0 DO
INT pn = number[ p - 1 ];
INT p1 = number[ p - 1 ];
INT next := find next( pn, n, number[ p ], used );
INT current = number[ p ];
⚫
INT next := current + 2;
⚫
WHILE IF next >= n THEN FALSE ELSE NOT prime[ p1 + next ] OR used[ next ] FI DO
⚫
next +:= 2
⚫
OD;
⚫
IF next >= n THEN next := 0 FI;
IF p = n - 1 THEN
IF p = n - 1 THEN
# we are at the final number before n #
# we are at the final number before n #
WHILE IF next = 0 THEN FALSE ELSE NOT prime pair[ next, n ] FI DO
# it must be the final even/odd number preceded by the final odd/even number #
next := find next( pn, n, next, used )
IF next /= 0 THEN
OD
# possible solution #
⚫
IF prime[ next + n ] THEN
⚫
# found a solution #
⚫
count +:= 1;
⚫
IF print solution THEN
⚫
FOR i TO n - 2 DO
⚫
print( ( whole( number[ i ], -3 ) ) )
⚫
OD;
⚫
print( ( whole( next, -3 ), whole( n, - 3 ), newline ) );
⚫
print solution := FALSE
⚫
FI
⚫
FI;
⚫
next := 0
⚫
FI;
⚫
# backtrack for more solutions #
⚫
p -:= 1
# here will be a further backtrack as next is 0 ( there could only be one possible number at p - 1 ) #
FI;
FI;
IF next /= 0 THEN
IF next /= 0 THEN
# have a/another number that can appear at p #
# have a/another number that can appear at p #
used[ number[ p ] ] := FALSE;
used[ current ] := FALSE;
used[ next ] := TRUE;
used[ next ] := TRUE;
number[ p ] := next;
number[ p ] := next;
IF p < n - 1 THEN
p +:= 1
# haven't found all the intervening digits yet #
p +:= 1;
number[ p ] := 0
ELSE
⚫
# found a solution #
⚫
count +:= 1;
⚫
IF count = 1 AND print solution THEN
FOR i TO n DO
⚫
print( ( whole( number[ i ], -3 ) ) )
OD;
print( ( newline ) )
FI;
⚫
# backtrack for more solutions #
used[ number[ p ] ] := FALSE;
⚫
number[ p ] := 0;
⚫
p -:= 1
⚫
FI
ELIF p <= 2 THEN
ELIF p <= 2 THEN
# no more solutions #
# no more solutions #
p := n
p := 0
ELSE
ELSE
# can't find a number for this position, backtrack #
# can't find a number for this position, backtrack #
used[ number[ p ] ] := FALSE;
used[ number[ p ] ] := FALSE;
number[ p ] := 0;
number[ p ] := p MOD 2;
p -:= 1
p -:= 1
FI
FI
Line 110: Line 94:
[ 2 : max number ]INT arrangements;
[ 2 : max number ]INT arrangements;
FOR n FROM LWB arrangements TO UPB arrangements DO
FOR n FROM LWB arrangements TO UPB arrangements DO
arrangements[ n ] := count arrangements( n, TRUE )
arrangements[ n ] := count arrangements( n )
OD;
OD;
FOR n FROM LWB arrangements TO UPB arrangements DO
FOR n FROM LWB arrangements TO UPB arrangements DO
Line 116: Line 100:
OD;
OD;
print( ( newline ) )
print( ( newline ) )
END
END</lang>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Retrieved from "https://rosettacode.org/wiki/Prime_triangle"