Prime triangle: Difference between revisions
Added FreeBASIC
(Created Nim solution.) |
(Added FreeBASIC) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 129:
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
{{trans|Visual Basic .NET}}
<syntaxhighlight lang="vbnet">Dim Shared As Uinteger maxNumber = 20 ' Largest number we will consider.
Dim Shared As Uinteger prime(2 * maxNumber) ' prime sieve.
Function countArrangements(Byval n As Uinteger) As Uinteger
Dim As Uinteger i
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 = 1 To n
Print Using "###"; i;
Next i
Print
Return 1
Else
' 4 or more - must find the solutions.
Dim As Boolean printSolution = True
Dim As Boolean used(n)
Dim As Uinteger number(n)
' 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 = 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 As Uinteger count = 0
Dim As Uinteger p = 2
Do While p > 0
Dim As Uinteger p1 = number(p - 1)
Dim As Uinteger current = number(p)
Dim As Uinteger sgte = current + 2
Do While sgte < n Andalso (Not prime(p1 + sgte) Or used(sgte))
sgte += 2
Loop
If sgte >= n Then
sgte = 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 sgte <> 0 Then
' Possible solution.
If prime(sgte + n) Then
' Found a solution.
count += 1
If printSolution Then
For i = 1 To n - 2
Print Using "###"; number(i);
Next i
Print Using "###"; sgte; n
printSolution = False
End If
End If
sgte = 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 sgte <> 0 Then
' have a/another number that can appear at p.
used(current) = False
used(sgte) = True
number(p) = sgte
' 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
Dim As Integer i, s, n
prime(2) = True
For i = 3 To Ubound(prime) Step 2
prime(i) = True
Next i
For i = 3 To Cint(Sqr(Ubound(prime))) Step 2
If prime(i) Then
For s = i * i To Ubound(prime) Step i + i
prime(s) = False
Next s
End If
Next i
Dim As Integer arrangements(maxNumber)
For n = 2 To Ubound(arrangements)
arrangements(n) = countArrangements(n)
Next n
For n = 2 To Ubound(arrangements)
Print arrangements(n);
Next n
Print
Sleep</syntaxhighlight>
{{out}}
<pre>Same as Visual Basic .NET entry.</pre>
==={{header|Visual Basic .NET}}===
{{Trans|ALGOL 68}}
Line 1,536 ⟶ 1,647:
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
"9.7s"
</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">
from numpy import array
# for Rosetta Code by MG - 20230312
def is_prime(n: int) -> bool:
assert n < 64
return ((1 << n) & 0x28208a20a08a28ac) != 0
def prime_triangle_row(a: array, start: int, length: int) -> bool:
if length == 2:
return is_prime(a[0] + a[1])
for i in range(1, length - 1, 1):
if is_prime(a[start] + a[start + i]):
a[start + i], a[start + 1] = a[start + 1], a[start + i]
if prime_triangle_row(a, start + 1, length - 1):
return True
a[start + i], a[start + 1] = a[start + 1], a[start + i]
return False
def prime_triangle_count(a: array, start: int, length: int) -> int:
count: int = 0
if length == 2:
if is_prime(a[start] + a[start + 1]):
count += 1
else:
for i in range(1, length - 1, 1):
if is_prime(a[start] + a[start + i]):
a[start + i], a[start + 1] = a[start + 1], a[start + i]
count += prime_triangle_count(a, start + 1, length - 1)
a[start + i], a[start + 1] = a[start + 1], a[start + i]
return count
def print_row(a: array):
if a == []:
return
print("%2d"% a[0], end=" ")
for x in a[1:]:
print("%2d"% x, end=" ")
print()
for n in range(2, 21):
tr: array = [_ for _ in range(1, n + 1)]
if prime_triangle_row(tr, 0, n):
print_row(tr)
print()
for n in range(2, 21):
tr: array = [_ for _ in range(1, n + 1)]
if n > 2:
print(" ", end="")
print(prime_triangle_count(tr, 0, n), end="")
print()
</syntaxhighlight>
{{out}}
<pre>
1 2
1 2 3
1 2 3 4
1 2 3 4 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 6 5 8 9 10 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 5 12 11 8 9 10 13 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 11 18 19 20
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
</pre>
Line 1,797 ⟶ 1,987:
{{libheader|Wren-fmt}}
Takes around 18.7 seconds which is fine for Wren.
<syntaxhighlight lang="
var canFollow = []
Line 1,876 ⟶ 2,066:
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
</pre>
| |||