Ormiston pairs: Difference between revisions
Added C++ solution
(→{{header|ALGOL 68}}: Simplify and Improve using ideas from the Wren and XPL0 samples.) |
(Added C++ solution) |
||
Line 113:
3722 Ormiston pairs below 10000000
53369 non-Ormiston "0 MOD 18" pairs bwlow 10000000
</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <algorithm>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <vector>
std::vector<bool> prime_sieve(int limit) {
std::vector<bool> sieve(limit, true);
if (limit > 0)
sieve[0] = false;
if (limit > 1)
sieve[1] = false;
for (int i = 4; i < limit; i += 2)
sieve[i] = false;
for (int p = 3, sq = 9; sq < limit; p += 2) {
if (sieve[p]) {
for (int q = sq; q < limit; q += p << 1)
sieve[q] = false;
}
sq += (p + 1) << 2;
}
return sieve;
}
class digit_set {
public:
explicit digit_set(int n) {
for (; n > 0; n /= 10)
++count_[n % 10];
}
bool operator==(const digit_set& other) const {
return std::equal(count_, count_ + 10, other.count_);
}
private:
int count_[10] = {};
};
int main() {
const int limit = 100000000;
std::vector<bool> sieve = prime_sieve(limit);
int count = 0, count1 = 0, count2 = 0;
std::cout << "First 30 Ormiston pairs:\n";
for (int p1 = 0, p2 = 0; p2 < limit; ++p2) {
if (!sieve[p2])
continue;
if (digit_set(p2) == digit_set(p1)) {
if (count1 == 0 && p2 > 1000000)
count1 = count;
if (count2 == 0 && p2 > 10000000)
count2 = count;
++count;
if (count <= 30)
std::cout << '(' << std::setw(5) << p1 << ", " << std::setw(5)
<< p2 << ')' << (count % 3 == 0 ? '\n' : ' ');
}
p1 = p2;
}
std::cout << "\nNumber of Ormiston pairs < 1,000,000: " << count1 << '\n';
std::cout << "Number of Ormiston pairs < 10,000,000: " << count2 << '\n';
std::cout << "Number of Ormiston pairs < 100,000,000: " << count << '\n';
}</syntaxhighlight>
{{out}}
<pre>
First 30 Ormiston pairs:
( 1913, 1931) (18379, 18397) (19013, 19031)
(25013, 25031) (34613, 34631) (35617, 35671)
(35879, 35897) (36979, 36997) (37379, 37397)
(37813, 37831) (40013, 40031) (40213, 40231)
(40639, 40693) (45613, 45631) (48091, 48109)
(49279, 49297) (51613, 51631) (55313, 55331)
(56179, 56197) (56713, 56731) (58613, 58631)
(63079, 63097) (63179, 63197) (64091, 64109)
(65479, 65497) (66413, 66431) (74779, 74797)
(75913, 75931) (76213, 76231) (76579, 76597)
Number of Ormiston pairs < 1,000,000: 382
Number of Ormiston pairs < 10,000,000: 3722
Number of Ormiston pairs < 100,000,000: 34901
</pre>
| |||