Rosetta Code

Prime triangle: Difference between revisions

Page Discussion

Prime triangle (view source)

Revision as of 01:24, 3 March 2024

8,755 bytes added ,  2 months ago
Added FreeBASIC
(→‎{{header|Perl}}: prepend Freepascal)
(Added FreeBASIC)
 
(7 intermediate revisions by 4 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,163 ⟶ 1,274:
{1, 1, 1, 1, 1, 2, 4, 7, 24, 80, 216, 648, 1304, 3392, 13808, 59448, 155464, 480728, 1588162}</pre>
 
=={{header|Nim}}==
{{trans|C}}
<syntaxhighlight lang="Nim">import std/[monotimes, strutils, times]
 
const IsPrime = [false, false, true, true, false, true, false, true,
false, false, false, true, false, true, false, false,
false, true, false, true, false, false, false, true,
false, false, false, false, false, true, false, true,
false, false, false, false, false, true, false, false,
false, true, false, true, false, false, false, true,
false, false, false, false, false, true, false, false,
false, false, false, true, false, true, false, false]
 
type TriangleRow = openArray[Natural]
 
template isPrime(n: Natural): bool = IsPrime[n]
 
func primeTriangleRow(a: var TriangleRow): bool =
if a.len == 2:
return isPrime(a[0] + a[1])
for i in countup(1, a.len - 2, 2):
if isPrime(a[0] + a[i]):
swap a[i], a[1]
if primeTriangleRow(a.toOpenArray(1, a.high)):
return true
swap a[i], a[1]
 
func primeTriangleCount(a: var TriangleRow): Natural =
if a.len == 2:
if isPrime(a[0] + a[1]):
inc result
else:
for i in countup(1, a.len - 2, 2):
if isPrime(a[0] + a[i]):
swap a[i], a[1]
inc result, primeTriangleCount(a.toOpenArray(1, a.high))
swap a[i], a[1]
 
proc print(a: TriangleRow) =
if a.len == 0: return
for i, n in a:
if n > 0: stdout.write ' '
stdout.write align($n, 2)
stdout.write '\n'
 
let start = getMonoTime()
for n in 2..20:
var a = newSeq[Natural](n)
for i in 0..<n:
a[i] = i + 1
if a.primeTriangleRow:
print a
echo()
for n in 2..20:
var a = newSeq[Natural](n)
for i in 0..<n:
a[i] = i + 1
if n > 2: stdout.write " "
stdout.write a.primeTriangleCount
echo '\n'
 
echo "Elapsed time: ", (getMonoTime() - start).inMilliseconds, " ms"
</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
 
Elapsed time: 535 ms
</pre>
 
=={{header|Pascal}}==
Line 1,447 ⟶ 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,708 ⟶ 1,987:
{{libheader|Wren-fmt}}
Takes around 18.7 seconds which is fine for Wren.
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
 
var canFollow = []
Jjuanhdez
2,122

edits

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