Последовательности простых чисел, сумма которых также проста

Если мы с помощью решета Эратосфена проверим, существуют ли такие цепочки последовательных простых чисел, что их сумма также является простым числом, в пределах счёта до одного миллиарда мы обнаружим только одну такую цепочку - числа 2 и 3. Просто потому, что все простые числа больше пяти заканчиваются на 1, 3, 7 или 9, а любые суммы этих цифр дают чётное число.

Кстати, заодно пополним и наш список простых чисел до границы поиска в один миллиард.

Программы из заметки проверялись в консоли актуальной сборки Visual Studio 2019.

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

typedef uint64_t integer;

class prime_sieve {
 //Простое решето Эратосфена. См. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
public:
 explicit prime_sieve(integer);
 bool is_prime(integer) const;
private:
 vector <bool> is_prime_;
};

inline prime_sieve::prime_sieve(integer limit) {
 limit = max(integer(3), limit);
 is_prime_.resize(limit / 2, true);
 for (integer p = 3; p * p <= limit; p += 2) {
  if (is_prime_[p / 2 - 1]) {
   integer inc = 2 * p;
   for (integer q = p * p; q <= limit; q += inc)
    is_prime_[q / 2 - 1] = false;
  }
 }
}

inline bool prime_sieve::is_prime(size_t n) const {
 if (n == 2) return true;
 if (n < 2 || n % 2 == 0) return false;
 return is_prime_.at(n / 2 - 1);
}

int main() {
 vector <integer> pf;
 const integer limit = 1000000000; //Верхняя граница поиска
 cout << "Sieve of Eratosthenes calculation, please wait..." << endl;
 prime_sieve sieve(limit);
 ofstream f("simple.txt");
 if (!f) {
  cout << "Can't create simple.txt, check permissions, please" << endl;
  return 1;
 }

 integer sum = 0;
 for (integer p = 2; p <= limit; p++) {
  if (!sieve.is_prime(p)) continue;
  f << p << endl;
  sum += p;
  if (sieve.is_prime(sum)) {
   pf.push_back (p);
  }
  else {
   if (pf.size() > 1) {
    for (auto i = pf.begin(); i != pf.end(); i++) cout << *i << ' ';
    cout << '('<< pf.size() << ')' << endl;
   }
   pf.clear();
   pf.push_back(p);
   sum = p;
  }
 }
 f.close();
 return 0;
}

 Скачать с Яндекс-диска список простых чисел от двух до миллиарда, файл .txt в архиве .zip, объём архива 122 Мб

Всего в этих пределах нашлось 50 847 534 простых числа.

Однако задачу можно видоизменить, зафиксировав начало цепочки на каком-либо простом числе, скажем, двойке, и продолжая прибавлять значения очередных простых чисел, пока сумма тоже не станет простой. Тогда имеет смысл посчитать, сколько цепочек начинается с простого числа N в заданных пределах счёта, допустим, среди K следующих за N простых чисел.

Ниже показана только примитивная версия подсчёта цепочки, начинающейся с двойки и включающей следующие 100 простых чисел. Обратите внимание, что размер решета из-за необходимости проверки на простоту сумм простых чисел должен быть сильно избыточен или же вторую проверку следует делать без решета.

#include <iostream>
#include <vector>
using namespace std;

typedef uint64_t integer;

class prime_sieve {
 //Простое решето Эратосфена. См. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
public:
 explicit prime_sieve(integer);
 bool is_prime(integer) const;
private:
 vector <bool> is_prime_;
};

inline prime_sieve::prime_sieve(integer limit) {
 limit = max(integer(3), limit);
 is_prime_.resize(limit / 2, true);
 for (integer p = 3; p * p <= limit; p += 2) {
  if (is_prime_[p / 2 - 1]) {
   integer inc = 2 * p;
   for (integer q = p * p; q <= limit; q += inc)
    is_prime_[q / 2 - 1] = false;
  }
 }
}

inline bool prime_sieve::is_prime(size_t n) const {
 if (n == 2) return true;
 if (n < 2 || n % 2 == 0) return false;
 return is_prime_.at(n / 2 - 1);
}

int main() {
 const integer limit = 100; //Сколько следующих простых учитываем

 cout << "Sieve of Eratosthenes calculation, please wait..." << endl;
 prime_sieve sieve(limit*1000);
 
 integer sum = 0, start = 2, num = 0, all = 0;
 for (integer p = 2; num <= limit; p++) {
  if (!sieve.is_prime(p)) continue;
  num++;
  sum += p;
  if (sieve.is_prime(sum)) {
   cout << "The sum of " << num << " primes in [" << start << ", "<< p << "] is " 
    << sum << " which is also prime" << endl;
   all++;
  }
 }
 cout << "There are " << all << " summerized primes from " << start <<
  " among the next " << limit << endl;
 return 0;
}

Sieve of Eratosthenes calculation, please wait...
The sum of 1 primes in [2, 2] is 2 which is also prime
The sum of 2 primes in [2, 3] is 5 which is also prime
The sum of 4 primes in [2, 7] is 17 which is also prime
The sum of 6 primes in [2, 13] is 41 which is also prime
The sum of 12 primes in [2, 37] is 197 which is also prime
The sum of 14 primes in [2, 43] is 281 which is also prime
The sum of 60 primes in [2, 281] is 7699 which is also prime
The sum of 64 primes in [2, 311] is 8893 which is also prime
The sum of 96 primes in [2, 503] is 22039 which is also prime
The sum of 100 primes in [2, 541] is 24133 which is also prime
There are 10 summerized primes from 2 among the next 100

Это задача из списка задач на простые числа

20.10.2021, 11:15 [845 просмотров]