Anaprimes: Difference between revisions
Added C++ solution
(→{{header|Wren}}: Now uses an insertion sort rather than the built-in quicksort. About 9% quicker than before.) |
(Added C++ solution) |
||
Line 30:
=={{header|C++}}==
{{libheader|Primesieve}}
This takes about 70 seconds on my system. Memory usage is 4G.
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>
#include <primesieve.hpp>
class digit_set {
public:
digit_set() {}
explicit digit_set(uint64_t n) {
for (; n > 0; n /= 10)
++count_[n % 10];
}
bool operator==(const digit_set& other) const {
return std::equal(count_, count_ + 10, other.count_);
}
bool operator<(const digit_set& other) const {
return std::lexicographical_compare(other.count_, other.count_ + 10,
count_, count_ + 10);
}
private:
int count_[10] = {};
};
int main() {
std::cout.imbue(std::locale(""));
primesieve::iterator pi;
using map_type = std::map<digit_set, std::vector<uint64_t>>;
map_type anaprimes;
for (uint64_t limit = 1000; limit <= 10000000000;) {
uint64_t prime = pi.next_prime();
if (prime > limit) {
size_t max_length = 0;
std::vector<map_type::iterator> groups;
for (auto i = anaprimes.begin(); i != anaprimes.end(); ++i) {
if (i->second.size() > max_length) {
groups.clear();
max_length = i->second.size();
}
if (max_length == i->second.size())
groups.push_back(i);
}
std::cout << "Largest group(s) of anaprimes before " << limit
<< ": " << max_length << " members:\n";
for (auto i : groups) {
std::cout << " First: " << i->second.front()
<< " Last: " << i->second.back() << '\n';
}
std::cout << '\n';
anaprimes.clear();
limit *= 10;
}
anaprimes[digit_set(prime)].push_back(prime);
}
}</syntaxhighlight>
{{out}}
<pre>
Largest group(s) of anaprimes before 1,000: 4 members:
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Largest group(s) of anaprimes before 10,000: 11 members:
First: 1,237 Last: 7,321
First: 1,279 Last: 9,721
Largest group(s) of anaprimes before 100,000: 39 members:
First: 13,789 Last: 98,731
Largest group(s) of anaprimes before 1,000,000: 148 members:
First: 123,479 Last: 974,213
Largest group(s) of anaprimes before 10,000,000: 731 members:
First: 1,235,789 Last: 9,875,321
Largest group(s) of anaprimes before 100,000,000: 4,333 members:
First: 12,345,769 Last: 97,654,321
Largest group(s) of anaprimes before 1,000,000,000: 26,519 members:
First: 102,345,697 Last: 976,542,103
Largest group(s) of anaprimes before 10,000,000,000: 152,526 members:
First: 1,123,465,789 Last: 9,876,543,211
</pre>
=={{header|jq}}==
| |||