Prime triangle: Difference between revisions
→{{header|ALGOL 68}}: Use Nigel's observation that the numbers must alternate between even and odd, simplify
m (C - minor edit) |
(→{{header|ALGOL 68}}: Use Nigel's observation that the numbers must alternate between even and odd, simplify) |
||
Line 8:
As Algol 68G under Windows is fully interpreted, a reduced number of rows is produced.
<lang algol68>BEGIN # find solutions to the "Prime Triangle" - a triangle of numbers that sum to primes #
INT max number = 18; # largest number we will consider #
# construct a primesieve and from that a table of pairs of numbers whose sum is prime #
Line 32 ⟶ 31:
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 := current + 1;▼
WHILE IF result >= n THEN FALSE ELSE NOT prime pair[ i, result ] OR used[ result ] FI DO
OD;
IF result >= n
END # find next # ;
# returns the number of possible arrangements of the integers for a row in the prime triangle #
Line 52 ⟶ 54:
[ 0 : n ]BOOL used;
[ 0 : n ]INT number;
▲ [ 0 : n ]INT position;
FOR i FROM 0 TO n DO
used[ i ] := FALSE;
number[ i ] := 0
OD;
# the triangle row must have 1 in the leftmost and n in the rightmost elements #
Line 66:
WHILE p < n DO
INT pn = number[ p - 1 ];
INT next := find next( pn, n,
IF p = n - 1 THEN
# we are at the final number before n #
WHILE IF next = 0 THEN FALSE ELSE NOT prime pair[ next, n ] FI DO
OD
FI;
IF next /= 0 THEN
# have a/another number that can appear at p #
used[
▲ number[ p ] := next;
IF p < n - 1 THEN
# haven't found all the intervening digits yet #
Line 94 ⟶ 92:
FI;
# backtrack for more solutions #
used[
p -:= 1
FI
Line 103 ⟶ 101:
ELSE
# can't find a number for this position, backtrack #
used[
p -:= 1
FI
Line 118 ⟶ 116:
OD;
print( ( newline ) )
END
</lang>
{{out}}
<pre>
| |||