Rosetta Code

Prime triangle: Difference between revisions

Page Discussion

Prime triangle (view source)

Revision as of 18:37, 23 April 2022

579 bytes removed ,  2 years ago
→‎{{header|ALGOL 68}}: Slight simplification
(→‎{{header|Go}}: Updated in line with Phix example of which this is a translation.)
(→‎{{header|ALGOL 68}}: Slight simplification)
Line 20:
FI
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 #
PROC count arrangements = ( INT n, BOOL print solution )INT:
IF n < 2 THEN # no solutions for n < 2 # 0
ELIF n < 4 THEN
# for 2 and 3. there is only 1 solution: 1, 2 and 1, 2, 3 #
IFFOR i TO n DO print( ( whole( i, -3 ) ) ) OD; print( ( newline solution) THEN);
FOR i TO n DO print( ( whole( i, -3 ) ) ) OD; print( ( newline ) )▼
FI;▼
1
ELSE
# 4 or more - must find the solutions #
BOOL print solution := FITRUE;▼
[ 0 : n ]BOOL used;
[ 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
used[ i ] := FALSE;
number[ i ] := 0i MOD 2
OD;
▲ prime pair used[ a, 1 ] := FALSETRUE;
▲ # the triangle row must have 1 in the leftmost and n in the rightmost elements #
number[ 1n ] := 1; used[ 1 ] := TRUEn;
numberused[ n ] := n; used[ n ] := TRUE;
# find the intervening numbers and count the solutions #
INT count := 0;
INT p := 2;
WHILE p <> n0 DO
INT pnp1 = number[ p - 1 ];
INT nextcurrent := findnumber[ next(p pn, n, number[ p ], used );
▲ INT result := IF current >INT 0next THEN := current + 2;
▲ WHILE IF resultnext >= n THEN FALSE ELSE NOT prime pair[ i,p1 + resultnext ] OR used[ resultnext ] FI DO
▲ result next +:= 2
▲ OD;
▲ IF resultnext >= n THEN 0next ELSE:= result0 FI;
IF p = n - 1 THEN
# we are at the final number before n #
WHILE# IFit nextmust =be 0the THENfinal FALSEeven/odd ELSEnumber NOTpreceded primeby pair[the next,final nodd/even ]number FI DO#
IF next :/= find next( pn, n, next, used0 )THEN
OD # possible solution #
▲ prime pair[ a, b ] := IF prime[ anext + bn ] THEN
# found a solution #▼
count +:= 1;▼
IF count = 1 ANDIF print solution THEN▼
▲ ELSE FOR i TO n - 2 3DO
print( ( whole( number[ i ], -3 ) ) )▼
▲ ELIF ODD i THEN 2OD;
▲ FOR i TO n DO print( ( whole( inext, -3 ), )whole( )n, OD;- print(3 (), newline ) );
number[ p print ]solution := 0;FALSE▼
▲ FI;
▲ FI;
▲ END # find next #:= ;0
▲ OD 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;
IF next /= 0 THEN
# have a/another number that can appear at p #
used[ number[ p ]current ] := FALSE;
used[ next ] := TRUE;
number[ p ] := next;
IF p < n -+:= 1 THEN
# 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
# no more solutions #
p := n0
ELSE
# can't find a number for this position, backtrack #
used[ number[ p ] ] := FALSE;
number[ p ] := 0p MOD 2;
p -:= 1
FI
Line 110 ⟶ 94:
[ 2 : max number ]INT arrangements;
FOR n FROM LWB arrangements TO UPB arrangements DO
arrangements[ n ] := count arrangements( n, TRUE )
OD;
FOR n FROM LWB arrangements TO UPB arrangements DO
Line 116 ⟶ 100:
OD;
print( ( newline ) )
END</lang>
</lang>
{{out}}
<pre>
Tigerofdarkness
3,044

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/320462"