Prime triangle: Difference between revisions

=={{header|Java}}==

<lang java>public class PrimeTriangle {

public static void main(String[] args) {

long start = System.currentTimeMillis();

for (int i = 2; i <= 20; ++i) {

int[] a = new int[i];

for (int j = 0; j < i; ++j)

a[j] = j + 1;

if (findRow(a, 0, i))

printRow(a);

}

System.out.println();

StringBuilder s = new StringBuilder();

for (int i = 2; i <= 20; ++i) {

int[] a = new int[i];

for (int j = 0; j < i; ++j)

a[j] = j + 1;

if (i > 2)

s.append(" ");

s.append(countRows(a, 0, i));

}

System.out.println(s);

long finish = System.currentTimeMillis();

System.out.printf("\nElapsed time: %d milliseconds\n", finish - start);

}

private static void printRow(int[] a) {

for (int i = 0; i < a.length; ++i) {

if (i != 0)

System.out.print(" ");

System.out.printf("%2d", a[i]);

}

System.out.println();

}

private static boolean findRow(int[] a, int start, int length) {

if (length == 2)

return isPrime(a[start] + a[start + 1]);

for (int i = 1; i + 1 < length; ++i) {

if (isPrime(a[start] + a[start + i])) {

swap(a, start + i, start + 1);

if (findRow(a, start + 1, length - 1))

return true;

swap(a, start + i, start + 1);

}

}

return false;

}

private static int countRows(int[] a, int start, int length) {

int count = 0;

if (length == 2) {

if (isPrime(a[start] + a[start + 1]))

++count;

} else {

for (int i = 1; i + 1 < length; ++i) {

if (isPrime(a[start] + a[start + i])) {

swap(a, start + i, start + 1);

count += countRows(a, start + 1, length - 1);

swap(a, start + i, start + 1);

}

}

}

return count;

}

private static void swap(int[] a, int i, int j) {

int tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}

private static boolean isPrime(int n) {

return ((1L << n) & 0x28208a20a08a28acL) != 0;

}

}</lang>

{{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: 977 milliseconds

</pre>