Prime triangle: Difference between revisions
Added FreeBASIC
m (→{{header|J}}: correctness) |
(Added FreeBASIC) |
||
(13 intermediate revisions by 9 users not shown) | |||
Line 2:
You will require a function f which when given an integer S will return a list of the arrangements of the integers 1 to S such that g<sub>1</sub>=1 g<sub>S</sub>=S and generally for n=1 to n=S-1 g<sub>n</sub>+g<sub>n+1</sub> is prime. S=1 is undefined. For S=2 to S=20 print f(S) to form a triangle. Then again for S=2 to S=20 print the number of possible arrangements of 1 to S meeting these requirements.
;See also
:* [[oeis:A036440|OEIS:A036440]]
=={{header|ALGOL 68}}==
Line 7 ⟶ 12:
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
As Algol 68G under Windows is fully interpreted, a reduced number of rows is produced.
<
INT max number = 18; # largest number we will consider #
# construct a primesieve and from that a table of pairs of numbers whose sum is prime #
Line 100 ⟶ 105:
OD;
print( ( newline ) )
END</
{{out}}
<pre>
Line 121 ⟶ 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|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}}
<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>
=={{header|C}}==
<
#include <stdbool.h>
#include <stdio.h>
Line 207 ⟶ 466:
printf("\nElapsed time: %f seconds\n", duration);
return 0;
}</
{{out}}
Line 239 ⟶ 498:
Number combinations are all stored in bit positions here. The <code>bpos()</code> functions returns the position index of the least significant bit in an integer. This code gains some speed, at the cost of total loss of readability. On the plus side, it has some bit manipulation tricks that may be interesting to some.
<
#include <stdint.h>
Line 330 ⟶ 589:
return 0;
}</
{{out}}
<pre> 1 2
Line 355 ⟶ 614:
=={{header|C++}}==
<
#include <chrono>
#include <iomanip>
Line 431 ⟶ 690:
std::chrono::duration<double> duration(end - start);
std::cout << "\nElapsed time: " << duration.count() << " seconds\n";
}</
{{out}}
Line 462 ⟶ 721:
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<
// Prime triangle. Nigel Galloway: April 12th., 2022
let fN i (g,(e,l))=e|>Seq.map(fun n->let n=i n in (n::g,List.partition(i>>(=)n) l))
Line 471 ⟶ 730:
{2..20}|>Seq.iter(fun n->(primeT>>Seq.head>>List.iter(printf "%3d"))n;printfn "");;
{2..20}|>Seq.iter(primeT>>Seq.length>>printf "%d "); printfn ""
</syntaxhighlight>
{{out}}
<pre>
Line 500 ⟶ 759:
Takes about 0.64 seconds.
{{trans|Phix}}
<
import "fmt"
Line 570 ⟶ 829:
}
fmt.Println()
}</
{{out}}
Line 603 ⟶ 862:
Implementation:
<
prime_pair_seqs=: {{ y add_plink (2}.i.y) add_plink^:(y-2) 1 }}</
Task example (displaying counts of number of valid sequences to the left, because that looks nice):
<
for_j.2}.i.1+y do.
N=. #seqs=. prime_pair_seqs j
Line 634 ⟶ 893:
155464 | 1 16 15 14 17 12 11 8 9 10 13 6 7 4 3 2 5 18
480728 | 1 18 13 16 15 14 17 12 11 8 9 10 7 6 5 2 3 4 19
1588162 | 1 18 19 12 17 14 15 16 13 10 9 8 11 2 5 6 7 4 3 20</
=={{header|Java}}==
<
public static void main(String[] args) {
long start = System.currentTimeMillis();
Line 711 ⟶ 970:
return ((1L << n) & 0x28208a20a08a28acL) != 0;
}
}</
{{out}}
Line 738 ⟶ 997:
Elapsed time: 833 milliseconds
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Adapted from [[#Wren|Wren]]'''
(gojq requires too much memory to complete the task.)
<syntaxhighlight lang=jq>
# $i and $j should be relevant integers (possibly negataive)
# Usage with an array-valued key: .key |= array_swap($i; $j)
def array_swap($i; $j):
if $i == $j then .
else .[$i] as $t
| .[$i] = .[$j]
| .[$j] = $t
end;
# For syntactic convenience
def swap($array; $i; $j):
$array | array_swap($i; $j);
def pmap:
reduce (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) as $i ([];
.[$i] = true) ;
# input: {bFirst, arrang, canFollow, emit}
# output: same + {res, emit, i, count}
def ptrs($res; $n; $done):
. + {$res, count: $done}
| .arrang[$done-1] as $ad
| if ($n - $done <= 1)
then if .canFollow[$ad-1][$n-1]
then if .bFirst
then .emit += [.arrang]
| .bFirst = false
else .
end
| .res += 1
else .
end
else .count += 1
| .count as $count
| reduce range($count - 1; $n - 1; 2) as $i (.;
.arrang[$i] as $ai
| if .canFollow[$ad-1][$ai-1]
then .arrang = swap(.arrang; $i; $count-1)
| ptrs(.res; $n; $count)
| .arrang = swap(.arrang; $i; $count-1)
else .
end )
end;
# Emit {emit, res} from the call to ptrs
def primeTriangle($n):
pmap as $pmap
| {}
| .canFollow = (reduce range(0;$n) as $i ([];
.[$i] = [range(0;$n) | false]
| reduce range(0;$n) as $j (.;
.[$i][$j] = $pmap[$i+$j+2] )))
| .bFirst = true
| .arrang = [range(1; 1+$n)]
| ptrs(0; $n; 1)
| {emit, res} ;
def task($n):
range(2;$n+1) as $i
| primeTriangle($i) ;
def task($n):
foreach (range(2;$n+1), null) as $i ({counts: [], emit: null};
if $i == null then .emit = "\n\(.counts)"
else primeTriangle($i) as $pt
| .counts += [$pt|.res]
| .emit = $pt.emit
end;
.emit);
task(20)[]
</syntaxhighlight>
{{output}}
<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>
=={{header|Julia}}==
=== Filter method ===
<
function primetriangle(nrows::Integer)
Line 773 ⟶ 1,135:
@time primetriangle(16)
</
<pre>
1 2
Line 797 ⟶ 1,159:
=== Generator method ===
Similar to the Phix entry.
<
function solverow(row, pos, avail)
Line 829 ⟶ 1,191:
println(" 1 2\n" * prod(rowstrings), "\n", counts)
end
</
<pre>
1 2
Line 856 ⟶ 1,218:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
FindPrimeTriangles[max_] :=
Module[{count = 0, firstsolution, primes, primeQ},
Line 888 ⟶ 1,250:
count
]
Table[FindPrimeTriangles[S],{S, 2, 20}]</
{{out}}
<pre>{1,2}
Line 912 ⟶ 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}}==
==={{header|Free Pascal}}===
Simple backtracking.Precaltulated like [[Prime_triangle#Phix]] Can_Follow by checking for sum gets prime.
<syntaxhighlight lang="pascal">
program PrimePyramid;
{$IFDEF FPC}
{$MODE delphi}{$Optimization ON,ALL}{$CodeAlign proc=32}
{$IFEND}
const
MAX = 21;//max 8 different SumToPrime : array[0..MAX,0..7] of byte;
//MAX = 57;//max 16 different SumToPrime : array[0..MAX,0..15] of byte;
cMaxAlign32 = (((MAX-1)DIV 32)+1)*32-1;//MAX > 0
type
tPrimeRange = set of 0..127;
var
SetOfPrimes :tPrimeRange =[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127];
SumToPrime : array[0..cMaxAlign32,0..7] of byte;
// SumToPrime : array[0..MAX,0..15] of byte;
SumToPrimeMaxIdx,
SumMaxIdx,
Solution,
FirstSolution : array[0..cMaxAlign32] of byte;
free : array[0..cMaxAlign32] of boolean;
maxused : integer;
digitcount,SolCount : integer;
procedure InitSumToPrime;
var
i,j,idx : integer;
begin
For i := 1 to MAX do
Begin
idx := 0;
For j := 1 to MAX do
If (i+j) in SetOfPrimes then
Begin
SumToPrime[i,idx] := j;
inc(idx);
end;
SumToPrimeMaxIdx[i] := idx;
end;
end;
procedure InitFree(maxused : integer);
var
i,j : Integer;
begin
For i := 0 to 1 do
Free[i] := false;
For i := 2 to maxused-1 do
Free[i] := true;
For i := maxused to MAX do
Free[i] := false;
// search maxidx of max neighour sum to prime
For i := 1 to maxused-1 do
begin
j := SumToPrimeMaxIdx[i]-1;
while SumToPrime[i,j] > maxused-1 do
j -= 1;
SumMaxIdx[i] := j+1;
end;
end;
procedure CountSolution(digit:integer);
begin
// check if maxused can follow
if (digit+maxused) in SetOfPrimes then
Begin
if solcount = 0 then
FirstSolution := Solution;
inc(solCount);
end;
end;
procedure checkDigits(digit:integer);
var
idx,nextDigit: integer;
begin
idx := 0;
repeat
nextDigit := SumToPrime[digit,idx];
if Free[nextdigit] then
Begin
Solution[digitcount] := nextDigit;
dec(digitcount);
IF digitcount = 0 then
CountSolution(nextDigit);
free[nextdigit]:= false;
checkDigits(nextdigit);
inc(digitcount);
free[nextdigit]:= true;
end;
inc(idx);
until idx >= SumMaxIdx[digit];
end;
var
i,j : integer;
Begin
InitSumToPrime;
writeln('number| count| first solution');
writeln(' 2| 1| 1 2');
For i := 3 to 20 do
Begin
maxused := i;
InitFree(i);
digitcount := i-2;
solCount := 0;
checkDigits(1);
write(i:4,'|',solcount:10,'| 1');
For j := i-2 downto 1 do
write( FirstSolution[j]:3);
writeln(i:3);
end;
end.
</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
number| count| first solution
2| 1| 1 2
3| 1| 1 2 3
4| 1| 1 2 3 4
5| 1| 1 4 3 2 5
6| 1| 1 4 3 2 5 6
7| 2| 1 4 3 2 5 6 7
8| 4| 1 2 3 4 7 6 5 8
9| 7| 1 2 3 4 7 6 5 8 9
10| 24| 1 2 3 4 7 6 5 8 9 10
11| 80| 1 2 3 4 7 10 9 8 5 6 11
12| 216| 1 2 3 4 7 10 9 8 5 6 11 12
13| 648| 1 2 3 4 7 6 5 12 11 8 9 10 13
14| 1304| 1 2 3 4 7 6 13 10 9 8 11 12 5 14
15| 3392| 1 2 3 4 7 6 13 10 9 8 11 12 5 14 15
16| 13808| 1 2 3 4 7 6 5 12 11 8 15 14 9 10 13 16
17| 59448| 1 2 3 4 7 6 5 12 11 8 9 10 13 16 15 14 17
18| 155464| 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18
19| 480728| 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19
20| 1588162| 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 19 18 11 20
Real time: 1.827 s User time: 1.794 s Sys. time: 0.021 s CPU share: 99.36 %
@home: real 0m0,679s</pre>
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<
use warnings;
use feature 'say';
Line 949 ⟶ 1,546:
}
say "\n" . join ' ', @count[2..$#count];</
{{out}}
<pre>1 2
Line 973 ⟶ 1,570:
{{libheader|Phix/online}}
Not sure this counts as particularly clever but by the sound of things it's quite a bit faster than the other entries so far. 😎<br> You can run this online [http://phix.x10.mx/p2js/prime_triangles.htm here] (expect a blank screen for about 24s).
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
Line 1,026 ⟶ 1,623:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">))</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 1,050 ⟶ 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,055 ⟶ 1,731:
Limit the upper threshold a bit to avoid multiple hours of pointless calculations. Even just up to 17 takes over 20 minutes.
<syntaxhighlight lang="raku"
my $lock = Lock.new;
put (1,2);
Line 1,079 ⟶ 1,755:
}
}
put "\n", @count[2..*];</
{{out}}
<pre>1 2
Line 1,102 ⟶ 1,778:
=={{header|Rust}}==
<
assert!(n < 64);
((1u64 << n) & 0x28208a20a08a28ac) != 0
Line 1,172 ⟶ 1,848:
let time = start.elapsed();
println!("\nElapsed time: {} milliseconds", time.as_millis());
}</
{{out}}
Line 1,202 ⟶ 1,878:
=={{header|Swift}}==
<
func isPrime(_ n: Int) -> Bool {
Line 1,278 ⟶ 1,954:
let endTime = CFAbsoluteTimeGetCurrent()
print("\nElapsed time: \(endTime - startTime) seconds")</
{{out}}
Line 1,305 ⟶ 1,981:
Elapsed time: 1.0268970727920532 seconds
</pre>
Line 1,453 ⟶ 1,987:
{{libheader|Wren-fmt}}
Takes around 18.7 seconds which is fine for Wren.
<
var canFollow = []
Line 1,507 ⟶ 2,041:
}
System.print()
System.print(counts.join(" "))</
{{out}}
|