Sexy primes: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Now uses 'fmt' module.) |
(Use boost::circular_buffer) |
||
Line 305: | Line 305: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{libheader|Boost}} |
|||
<lang cpp>#include < |
<lang cpp>#include <array> |
||
#include <iostream> |
|||
#include <vector> |
#include <vector> |
||
#include <boost/circular_buffer.hpp> |
|||
#include "sieve_of_eratosthenes.h" |
#include "sieve_of_eratosthenes.h" |
||
int main() |
int main() { |
||
{ |
|||
using std::cout; |
using std::cout; |
||
using std::vector; |
using std::vector; |
||
using boost::circular_buffer; |
|||
using group_buffer = circular_buffer<vector<int>>; |
|||
const int max = 1000035; |
const int max = 1000035; |
||
Line 324: | Line 328: | ||
sieve_of_eratosthenes sieve(array_size); |
sieve_of_eratosthenes sieve(array_size); |
||
std::array<int, max_group_size> group_count{0}; |
|||
vector< |
vector<group_buffer> groups(max_group_size, group_buffer(max_groups)); |
||
int unsexy_count = 0; |
int unsexy_count = 0; |
||
circular_buffer<int> unsexy_primes(max_unsexy); |
|||
for (int p = 2; p < max; ) |
for (int p = 2; p < max; ) { |
||
⚫ | |||
{ |
|||
⚫ | |||
{ |
|||
// if p + diff and p - diff aren't prime then p can't be sexy |
// if p + diff and p - diff aren't prime then p can't be sexy |
||
++unsexy_count; |
++unsexy_count; |
||
if (unsexy_primes.size() == max_unsexy) |
|||
unsexy_primes.erase(unsexy_primes.begin()); |
|||
unsexy_primes.push_back(p); |
unsexy_primes.push_back(p); |
||
} |
} else { |
||
else |
|||
{ |
|||
// find the groups of sexy primes that begin with p |
// find the groups of sexy primes that begin with p |
||
int group_size = 1; |
int group_size = 1; |
||
vector<int> group; |
vector<int> group; |
||
group.push_back(p); |
group.push_back(p); |
||
for (int i = 1; i < max_group_size; ++i) |
for (int i = 1; i < max_group_size; ++i) { |
||
{ |
|||
int next_p = p + i * diff; |
int next_p = p + i * diff; |
||
if (next_p >= max || !sieve.is_prime(next_p)) |
if (next_p >= max || !sieve.is_prime(next_p)) |
||
break; |
break; |
||
++group_size; |
|||
group.push_back(next_p); |
group.push_back(next_p); |
||
groups[group_size++].push_back(group); |
|||
if (v.size() == max_groups) |
|||
v.erase(v.begin()); |
|||
v.push_back(group); |
|||
} |
} |
||
for (int i = 1; i < group_size; ++i) |
for (int i = 1; i < group_size; ++i) |
||
Line 366: | Line 359: | ||
} |
} |
||
for (int size = 1; size < max_group_size; ++size) |
for (int size = 1; size < max_group_size; ++size) { |
||
{ |
|||
cout << "number of groups of size " << size + 1 << " is " << group_count[size] << '\n'; |
cout << "number of groups of size " << size + 1 << " is " << group_count[size] << '\n'; |
||
cout << "last " << groups[size].size() << " groups of size " << size + 1 << ":"; |
cout << "last " << groups[size].size() << " groups of size " << size + 1 << ":"; |
||
for (const vector<int>& group : groups[size]) |
for (const vector<int>& group : groups[size]) { |
||
{ |
|||
cout << " ("; |
cout << " ("; |
||
for (size_t i = 0; i < group.size(); ++i) |
for (size_t i = 0; i < group.size(); ++i) { |
||
{ |
|||
if (i > 0) |
if (i > 0) |
||
cout << ' '; |
cout << ' '; |
||
Line 383: | Line 373: | ||
cout << "\n\n"; |
cout << "\n\n"; |
||
} |
} |
||
cout << "number of unsexy primes is " << unsexy_count << '\n'; |
cout << "number of unsexy primes is " << unsexy_count << '\n'; |
||
cout << "last " << unsexy_primes.size() << " unsexy primes:"; |
cout << "last " << unsexy_primes.size() << " unsexy primes:"; |
||
Line 389: | Line 378: | ||
cout << ' ' << prime; |
cout << ' ' << prime; |
||
cout << '\n'; |
cout << '\n'; |
||
return 0; |
return 0; |
||
}</lang> |
}</lang> |