Prime triangle: Difference between revisions
Added C solution
(Added C++ solution) |
(Added C solution) |
||
Line 139:
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|C}}==
<lang c>#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <time.h>
bool is_prime(unsigned int n) {
assert(n < 64);
static bool isprime[] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0,
0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1,
0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0};
return isprime[n];
}
void swap(unsigned int* a, size_t i, size_t j) {
unsigned int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
bool prime_triangle(unsigned int* a, size_t length) {
if (length == 2)
return is_prime(a[0] + a[1]);
for (size_t i = 1; i + 1 != length; ++i) {
if (is_prime(a[0] + a[i])) {
swap(a, i, 1);
if (prime_triangle(a + 1, length - 1))
return true;
swap(a, i, 1);
}
}
return false;
}
void prime_triangle_count(unsigned int* a, size_t length, int* count) {
if (length == 2) {
if (is_prime(a[0] + a[1]))
++*count;
return;
}
for (size_t i = 1; i + 1 != length; ++i) {
if (is_prime(a[0] + a[i])) {
swap(a, i, 1);
prime_triangle_count(a + 1, length - 1, count);
swap(a, i, 1);
}
}
}
void print(unsigned int* a, size_t length) {
if (length == 0)
return;
printf("%2u", a[0]);
for (size_t i = 1; i < length; ++i)
printf(" %2u", a[i]);
printf("\n");
}
int main() {
clock_t start = clock();
for (unsigned int n = 2; n < 21; ++n) {
unsigned int a[n];
for (unsigned int i = 0; i < n; ++i)
a[i] = i + 1;
if (prime_triangle(a, n))
print(a, n);
}
printf("\n");
for (unsigned int n = 2; n < 21; ++n) {
unsigned int a[n];
for (unsigned int i = 0; i < n; ++i)
a[i] = i + 1;
int count = 0;
prime_triangle_count(a, n, &count);
if (n > 2)
printf(" ");
printf("%d", count);
}
printf("\n");
clock_t end = clock();
double duration = (end - start + 0.0) / CLOCKS_PER_SEC;
printf("\nElapsed time: %f seconds\n", duration);
return 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: 0.649755 seconds
</pre>
| |||