Prime triangle: Difference between revisions
Content added Content deleted
(→{{header|ALGOL 68}}: Use Nigel's observation that the numbers must alternate between even and odd, simplify) |
(→{{header|Visual Basic .NET}}: Incorporate Nigel's even/odd observation (see talk page)) |
||
Line 1,138: | Line 1,138: | ||
''' <returns>The next number that can follow i or 0 if there isn't one.</returns> |
''' <returns>The next number that can follow i or 0 if there isn't one.</returns> |
||
Public Function findNext(ByVal i As Integer, ByVal n As Integer, ByVal current As Integer, ByVal used() As Boolean) As Integer |
Public Function findNext(ByVal i As Integer, ByVal n As Integer, ByVal current As Integer, ByVal used() As Boolean) As Integer |
||
Dim result As Integer = current + |
Dim result As Integer = current + 2 |
||
' The numbers must alternate between even and odd in order for the sum to be prime. |
|||
⚫ | |||
result |
If i Mod 2 = 0 And result = 2 Then |
||
⚫ | |||
End If |
|||
⚫ | |||
⚫ | |||
Loop |
Loop |
||
If result >= n |
If result >= n Then |
||
result = 0 |
result = 0 |
||
End If |
End If |
||
Line 1,165: | Line 1,169: | ||
Dim used(n) As Boolean |
Dim used(n) As Boolean |
||
Dim number(n) As Integer |
Dim number(n) As Integer |
||
Dim position(n) As Integer |
|||
For i As Integer = 0 To n |
|||
⚫ | |||
⚫ | |||
' The triangle row must have 1 in the leftmost and n in the rightmost elements. |
' The triangle row must have 1 in the leftmost and n in the rightmost elements. |
||
number(1) = 1 |
number(1) = 1 |
||
Line 1,179: | Line 1,179: | ||
Do While p < n |
Do While p < n |
||
Dim pn As Integer = number(p - 1) |
Dim pn As Integer = number(p - 1) |
||
Dim [next] As Integer = findNext(pn, n, |
Dim [next] As Integer = findNext(pn, n, number(p), used) |
||
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. |
||
Do While If([next] = 0, False, Not primePair([next], n)) |
Do While If([next] = 0, False, Not primePair([next], n)) |
||
[next] = findNext(pn, n, [next], used) |
|||
[next] = findNext(pn, n, position(pn), used) |
|||
Loop |
Loop |
||
End If |
End If |
||
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( |
used(number(p)) = False |
||
position(pn) = [next] |
|||
used([next]) = True |
used([next]) = True |
||
number(p) = [next] |
number(p) = [next] |
||
Line 1,207: | Line 1,205: | ||
End If |
End If |
||
' Backtrack for more solutions. |
' Backtrack for more solutions. |
||
used( |
used(number(p)) = False |
||
position(pn) = 0 |
|||
number(p) = 0 |
number(p) = 0 |
||
p -= 1 |
p -= 1 |
||
Line 1,217: | Line 1,214: | ||
Else |
Else |
||
' Can't find a number for this position, backtrack. |
' Can't find a number for this position, backtrack. |
||
used( |
used(number(p)) = False |
||
position(pn) = 0 |
|||
number(p) = 0 |
number(p) = 0 |
||
p -= 1 |
p -= 1 |