Pierpont primes: Difference between revisions
m
More efficient implementation of n-smooth number generator
m (More efficient implementation of n-smooth number generator) |
|||
Line 365:
{{libheader|GMP}}
<lang cpp>#include <cassert>
#include <iomanip>
#include <iostream>
▲#include <set>
#include <vector>
#include <gmpxx.h>
Line 373:
using big_int = mpz_class;
bool is_prime(const big_int& n) {
return mpz_probab_prime_p(n.get_mpz_t(), 25);
}
template <typename integer>
class n_smooth_generator {
public:
explicit n_smooth_generator(
size_t size() const {
return results_.size();
private:
std::vector<
std::
std::vector<integer> results_;
std::vector<integer> queue_;
};
template <typename integer>
n_smooth_generator<integer>::n_smooth_generator(
for (
if (is_prime(p)) {▼
▲ {
▲ if (is_prime(p))
primes_.push_back(p);
queue_.push_back(p);
}
results_.push_back(1);
}
template <typename integer>
if (queue_[i] == last)
results_.push_back(*min_element(queue_.begin(), queue_.end()));
return
}
void print_vector(const std::vector<big_int>& numbers) {
for (size_t i = 0, n = numbers.size(); i < n; ++i) {
▲ for (size_t i = 0, n = numbers.size(); i < n; ++i)
▲ {
std::cout << std::setw(9) << numbers[i];
if ((i + 1) % 10 == 0)
Line 419 ⟶ 424:
}
int main() {
const int max = 250;
std::vector<big_int> first, second;
int count1 = 0;
int count2 = 0;
n_smooth_generator<big_int> smooth_gen(3);
big_int p1, p2;
while (count1 < max || count2 < max) {
big_int n = smooth_gen.next();
if (count1 < max && is_prime(n + 1)) {
▲ {
p1 = n + 1;
if (first.size() < 50)
Line 438 ⟶ 440:
++count1;
}
if (count2 < max && is_prime(n - 1)) {
p2 = n - 1;
if (second.size() < 50)
Line 454 ⟶ 455:
std::cout << "250th Pierpont prime of the first kind: " << p1 << '\n';
std::cout << "250th Pierpont prime of the second kind: " << p2 << '\n';
return 0;
}</lang>
| |||