Prime triangle: Difference between revisions
Content added Content deleted
(Added C++ solution) |
(Added C solution) |
||
Line 139: | Line 139: | ||
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 |
||
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 |
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> |
</pre> |
||