CalmoSoft primes: Difference between revisions
Added C++ solution
m (→{{header|Wren}}: Now uses new 'Fmt.va' method to abridge lists.) |
(Added C++ solution) |
||
Line 450:
7 + 11 + 13 + 17 + 19 + 23 + .. + 49999699 + 49999711 + 49999739 + 49999751 + 49999753 + 49999757 = 72,618,848,632,313
</pre>
=={{header|C++}}==
{{trans|Phix}}
{{libheader|Primesieve}}
<syntaxhighlight lang="cpp">#include <chrono>
#include <iostream>
#include <locale>
#include <numeric>
#include <sstream>
#include <primesieve.hpp>
bool is_prime(uint64_t n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
if (n % 5 == 0)
return n == 5;
static constexpr uint64_t wheel[] = {4, 2, 4, 2, 4, 6, 2, 6};
uint64_t p = 7;
for (;;) {
for (uint64_t w : wheel) {
if (p * p > n)
return true;
if (n % p == 0)
return false;
p += w;
}
}
}
template <typename Iterator>
std::string join(Iterator begin, Iterator end, std::string_view separator) {
std::ostringstream os;
if (begin != end) {
os << *begin++;
for (; begin != end; ++begin)
os << separator << *begin;
}
return os.str();
}
int main() {
std::cout.imbue(std::locale(""));
auto start = std::chrono::high_resolution_clock::now();
std::vector<uint64_t> primes;
uint64_t from = 0;
for (uint64_t limit : {100, 5000, 10000, 500000, 50000000}) {
primesieve::generate_primes(from, limit, &primes);
from = limit + 1;
uint64_t sum =
std::accumulate(primes.begin(), primes.end(), uint64_t(0));
size_t last = primes.size();
size_t longest = 1;
std::vector<std::pair<size_t, uint64_t>> starts;
for (size_t start = 0; start <= last - longest; ++start) {
uint64_t s = sum;
for (size_t finish = last; finish-- >= start + longest;) {
if (is_prime(s)) {
size_t length = finish - start + 1;
if (length > longest) {
longest = length;
starts.clear();
}
starts.emplace_back(start, s);
}
s -= primes[finish];
}
sum -= primes[start];
}
std::cout << "For primes up to " << limit << ":\n"
<< "The following sequence" << (starts.size() == 1 ? "" : "s")
<< " of " << longest << " consecutive primes yield"
<< (starts.size() == 1 ? "s" : "") << " a prime sum:\n";
for (auto [start, sum] : starts) {
auto begin = primes.begin() + start;
auto end = begin + longest;
const char* separator = " + ";
if (longest > 12) {
std::cout << join(begin, begin + 6, separator) << separator
<< "..." << separator
<< join(end - 6, end, separator);
} else {
std::cout << join(begin, end, separator);
}
std::cout << " = " << sum << '\n';
}
std::cout << '\n';
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration(end - start);
std::cout << "Elapsed time: " << duration.count() << " seconds\n";
}</syntaxhighlight>
{{out}}
<pre>
For primes up to 100:
The following sequence of 21 consecutive primes yields a prime sum:
7 + 11 + 13 + 17 + 19 + 23 + ... + 67 + 71 + 73 + 79 + 83 + 89 = 953
For primes up to 5,000:
The following sequence of 665 consecutive primes yields a prime sum:
7 + 11 + 13 + 17 + 19 + 23 + ... + 4957 + 4967 + 4969 + 4973 + 4987 + 4993 = 1,543,127
For primes up to 10,000:
The following sequences of 1,223 consecutive primes yield a prime sum:
3 + 5 + 7 + 11 + 13 + 17 + ... + 9883 + 9887 + 9901 + 9907 + 9923 + 9929 = 5,686,633
7 + 11 + 13 + 17 + 19 + 23 + ... + 9901 + 9907 + 9923 + 9929 + 9931 + 9941 = 5,706,497
For primes up to 500,000:
The following sequence of 41,530 consecutive primes yields a prime sum:
2 + 3 + 5 + 7 + 11 + 13 + ... + 499787 + 499801 + 499819 + 499853 + 499879 + 499883 = 9,910,236,647
For primes up to 50,000,000:
The following sequence of 3,001,117 consecutive primes yields a prime sum:
7 + 11 + 13 + 17 + 19 + 23 + ... + 49999699 + 49999711 + 49999739 + 49999751 + 49999753 + 49999757 = 72,618,848,632,313
Elapsed time: 0.0814633 seconds
</pre>
| |||