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 + 1
Dim result As Integer = current + 2
' The numbers must alternate between even and odd in order for the sum to be prime.
Do While result < n And (Not primePair(i, result) Or used(result))
result += 1
If i Mod 2 = 0 And result = 2 Then
result = 3
End If
Do While result < n AndAlso (Not primePair(i, result) Or used(result))
result += 2
Loop
Loop
If result >= n Or (Not primePair(i, result) Or used(result)) Then
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
position(i) = 1
Next i
' 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, position(pn), used)
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))
position(pn) = [next]
[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(position(pn)) = False
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(position(pn)) = False
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(position(pn)) = False
used(number(p)) = False
position(pn) = 0
number(p) = 0
number(p) = 0
p -= 1
p -= 1