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 <iostream>
<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);


vector<int> group_count(max_group_size);
std::array<int, max_group_size> group_count{0};
vector<vector<vector<int>>> groups(max_group_size);
vector<group_buffer> groups(max_group_size, group_buffer(max_groups));
int unsexy_count = 0;
int unsexy_count = 0;
vector<int> unsexy_primes;
circular_buffer<int> unsexy_primes(max_unsexy);


for (int p = 2; p < max; )
for (int p = 2; p < max; ) {
if (!sieve.is_prime(p + diff) && (p - diff < 2 || !sieve.is_prime(p - diff))) {
{
if (!sieve.is_prime(p + diff) && (p - diff < 2 || !sieve.is_prime(p - diff)))
{
// 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);
vector<vector<int>>& v = groups[group_size - 1];
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>