Prime triangle: Difference between revisions

</pre>

=={{header|C++}}==

<lang cpp>#include <cassert>

#include <chrono>

#include <iomanip>

#include <iostream>

#include <numeric>

#include <vector>

bool is_prime(unsigned int n) {

assert(n > 0 && n < 64);

return (1ULL << n) & 0x28208a20a08a28ac;

}

template <typename Iterator>

bool prime_triangle(Iterator begin, Iterator end) {

if (std::distance(begin, end) == 2)

return is_prime(*begin + *(begin + 1));

for (auto i = begin + 1; i + 1 != end; ++i) {

if (is_prime(*begin + *i)) {

std::iter_swap(i, begin + 1);

if (prime_triangle(begin + 1, end))

return true;

std::iter_swap(i, begin + 1);

}

}

return false;

}

template <typename Iterator>

void prime_triangle_count(Iterator begin, Iterator end, int& count) {

if (std::distance(begin, end) == 2) {

if (is_prime(*begin + *(begin + 1)))

++count;

return;

}

for (auto i = begin + 1; i + 1 != end; ++i) {

if (is_prime(*begin + *i)) {

std::iter_swap(i, begin + 1);

prime_triangle_count(begin + 1, end, count);

std::iter_swap(i, begin + 1);

}

}

}

template <typename Iterator>

void print(Iterator begin, Iterator end) {

if (begin == end)

return;

auto i = begin;

std::cout << std::setw(2) << *i++;

for (; i != end; ++i)

std::cout << ' ' << std::setw(2) << *i;

std::cout << '\n';

}

int main() {

auto start = std::chrono::high_resolution_clock::now();

for (unsigned int n = 2; n < 21; ++n) {

std::vector<unsigned int> v(n);

std::iota(v.begin(), v.end(), 1);

if (prime_triangle(v.begin(), v.end()))

print(v.begin(), v.end());

}

std::cout << '\n';

for (unsigned int n = 2; n < 21; ++n) {

std::vector<unsigned int> v(n);

std::iota(v.begin(), v.end(), 1);

int count = 0;

prime_triangle_count(v.begin(), v.end(), count);

if (n > 2)

std::cout << ' ';

std::cout << count;

}

std::cout << '\n';

auto end = std::chrono::high_resolution_clock::now();

std::chrono::duration<double> duration(end - start);

std::cout << "\nElapsed time: " << duration.count() << " seconds\n";

}</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.636331 seconds