Последовательности простых чисел, сумма которых также проста
Если мы с помощью решета Эратосфена проверим, существуют ли такие цепочки последовательных простых чисел, что их сумма также является простым числом, в пределах счёта до одного миллиарда мы обнаружим только одну такую цепочку - числа 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; }
Всего в этих пределах нашлось 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 [849 просмотров]