Pierpont primes: Difference between revisions

Content added Content deleted

Inline

@@ Line 365: / Line 365: @@
 {{libheader|GMP}}
 <lang cpp>#include <cassert>
+#include <algorithm>
 #include <iomanip>
 #include <iostream>
-#include <set>
 #include <vector>
 #include <gmpxx.h>
@@ Line 373: / Line 373: @@
 using big_int = mpz_class;
-bool is_prime(const big_int& n)
+bool is_prime(const big_int& n) {
-{
     return mpz_probab_prime_p(n.get_mpz_t(), 25);
 }
+template <typename integer>
-class n_smooth_generator
+class n_smooth_generator {
-{
 public:
-    explicit n_smooth_generator(int n);
+    explicit n_smooth_generator(size_t n);
-    big_int next();
+    integer next();
+    size_t size() const {
+        return results_.size();
+    }
 private:
-    std::vector<int> primes_;
+    std::vector<size_t> primes_;
-    std::set<big_int> numbers_;
+    std::vector<size_t> index_;
+    std::vector<integer> results_;
+    std::vector<integer> queue_;
 };
+template <typename integer>
-n_smooth_generator::n_smooth_generator(int n)
+n_smooth_generator<integer>::n_smooth_generator(size_t n) {
-{
-    for (int p = 2; p <= n; ++p)
+    for (size_t p = 2; p <= n; ++p) {
+        if (is_prime(p)) {
-    {
-        if (is_prime(p))
             primes_.push_back(p);
+            queue_.push_back(p);
+        }
     }
-    numbers_.insert(1);
+    index_.assign(primes_.size(), 0);
+    results_.push_back(1);
 }
+template <typename integer>
-big_int n_smooth_generator::next()
+integer n_smooth_generator<integer>::next() {
-{
-    assert(!numbers_.empty());
+    integer last = results_.back();
+    for (size_t i = 0, n = primes_.size(); i < n; ++i) {
-    big_int result = *numbers_.begin();
+        if (queue_[i] == last)
-    numbers_.erase(numbers_.begin());
-    for (auto prime : primes_)
+            queue_[i] = results_[++index_[i]] * primes_[i];
+    }
-        numbers_.insert(result * prime);
+    results_.push_back(*min_element(queue_.begin(), queue_.end()));
-    return result;
+    return last;
 }
-void print_vector(const std::vector<big_int>& numbers)
+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: / Line 424: @@
 }
-int main()
+int main() {
-{
     const int max = 250;
     std::vector<big_int> first, second;
     int count1 = 0;
     int count2 = 0;
-    n_smooth_generator smooth_gen(3);
+    n_smooth_generator<big_int> smooth_gen(3);
     big_int p1, p2;
-    while (count1 < max || count2 < max)
+    while (count1 < max || count2 < max) {
-    {
         big_int n = smooth_gen.next();
-        if (count1 < max && is_prime(n + 1))
+        if (count1 < max && is_prime(n + 1)) {
-        {
             p1 = n + 1;
             if (first.size() < 50)
@@ Line 438: / Line 440: @@
             ++count1;
         }
-        if (count2 < max && is_prime(n - 1))
+        if (count2 < max && is_prime(n - 1)) {
-        {
             p2 = n - 1;
             if (second.size() < 50)
@@ Line 454: / Line 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>