Prime triangle: Difference between revisions
Dialects of BASIC moved to the BASIC section.
(Dialects of BASIC moved to the BASIC section.) |
|||
Line 126:
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464
</pre>
=={{header|BASIC}}==
==={{header|Visual Basic .NET}}===
{{Trans|ALGOL 68}}
<syntaxhighlight lang="vbnet">Option Strict On
Option Explicit On
Imports System.IO
''' <summary>Find solutions to the "Prime Triangle" - a triangle of numbers that sum to primes.</summary>
Module vMain
Public Const maxNumber As Integer = 20 ' Largest number we will consider.
Dim prime(2 * maxNumber) As Boolean ' prime sieve.
''' <returns>The number of possible arrangements of the integers for a row in the prime triangle.</returns>
Public Function countArrangements(ByVal n As Integer) As Integer
If n < 2 Then ' No solutions for n < 2.
Return 0
ElseIf n < 4 Then
' For 2 and 3. there is only 1 solution: 1, 2 and 1, 2, 3.
For i As Integer = 1 To n
Console.Out.Write(i.ToString.PadLeft(3))
Next i
Console.Out.WriteLine()
Return 1
Else
' 4 or more - must find the solutions.
Dim printSolution As Boolean = true
Dim used(n) As Boolean
Dim number(n) As Integer
' 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 sums to be prime.
For i As Integer = 0 To n - 1
number(i) = i Mod 2
Next i
used(1) = True
number(n) = n
used(n) = True
' Find the intervening numbers and count the solutions.
Dim count As Integer = 0
Dim p As Integer = 2
Do While p > 0
Dim p1 As Integer = number(p - 1)
Dim current As Integer = number(p)
Dim [next] As Integer = current + 2
Do While [next] < n AndAlso (Not prime(p1 + [next]) Or used([next]))
[next] += 2
Loop
If [next] >= n Then
[next] = 0
End If
If p = n - 1 Then
' We are at the final number before n.
' It must be the final even/odd number preceded by the final odd/even number.
If [next] <> 0 Then
' Possible solution.
If prime([next] + n) Then
' Found a solution.
count += 1
If printSolution Then
For i As Integer = 1 To n - 2
Console.Out.Write(number(i).ToString.PadLeft(3))
Next i
Console.Out.WriteLine([next].ToString.PadLeft(3) & n.ToString.PadLeft(3))
printSolution = False
End If
End If
[next] = 0
End If
' Backtrack for more solutions.
p -= 1
' There will be a further backtrack as next is 0 ( there could only be one possible number at p - 1 ).
End If
If [next] <> 0 Then
' have a/another number that can appear at p.
used(current) = False
used([next]) = True
number(p) = [next]
' Haven't found all the intervening digits yet.
p += 1
ElseIf p <= 2 Then
' No more solutions.
p = 0
Else
' Can't find a number for this position, backtrack.
used(number(p)) = False
number(p) = p Mod 2
p -= 1
End If
Loop
Return count
End If
End Function
Public Sub Main
prime(2) = True
For i As Integer = 3 To UBound(prime) Step 2
prime(i) = True
Next i
For i As Integer = 3 To Convert.ToInt32(Math.Floor(Math.Sqrt(Ubound(prime)))) Step 2
If prime(i) Then
For s As Integer = i * i To Ubound(prime) Step i + i
prime(s) = False
Next s
End If
Next i
Dim arrangements(maxNumber) As Integer
For n As Integer = 2 To UBound(arrangements)
arrangements(n) = countArrangements(n)
Next n
For n As Integer = 2 To UBound(arrangements)
Console.Out.Write(" " & arrangements(n))
Next n
Console.Out.WriteLine()
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>
1 2
1 2 3
1 2 3 4
1 4 3 2 5
1 4 3 2 5 6
1 4 3 2 5 6 7
1 2 3 4 7 6 5 8
1 2 3 4 7 6 5 8 9
1 2 3 4 7 6 5 8 9 10
1 2 3 4 7 10 9 8 5 6 11
1 2 3 4 7 10 9 8 5 6 11 12
1 2 3 4 7 6 5 12 11 8 9 10 13
1 2 3 4 7 6 13 10 9 8 11 12 5 14
1 2 3 4 7 6 13 10 9 8 11 12 5 14 15
1 2 3 4 7 6 5 12 11 8 15 14 9 10 13 16
1 2 3 4 7 6 5 12 11 8 9 10 13 16 15 14 17
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 19 18 11 20
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
</pre>
Line 1,420 ⟶ 1,563:
Elapsed time: 1.0268970727920532 seconds
</pre>
| |||