46 lines
1.1 KiB
Text
46 lines
1.1 KiB
Text
#include <cmath>
|
|
#include <cstdint>
|
|
#include <iomanip>
|
|
#include <iostream>
|
|
#include <stdexcept>
|
|
#include <vector>
|
|
|
|
std::vector<bool> primes;
|
|
|
|
void initialise_primes(const int32_t& limit) {
|
|
primes.resize(limit);
|
|
for ( int32_t i = 2; i < limit; ++i ) {
|
|
primes[i] = true;
|
|
}
|
|
|
|
for ( int32_t n = 2; n < sqrt(limit); ++n ) {
|
|
for ( int32_t k = n * n; k < limit; k += n ) {
|
|
primes[k] = false;
|
|
}
|
|
}
|
|
}
|
|
|
|
int32_t goldbach_function(const int32_t& number) {
|
|
if ( number <= 2 || number % 2 == 1 ) {
|
|
throw std::invalid_argument("Argument must be even and greater than 2: " + std::to_string(number));
|
|
}
|
|
|
|
int32_t result = 0;
|
|
for ( int32_t i = 1; i <= number / 2; ++i ) {
|
|
if ( primes[i] && primes[number - i] ) {
|
|
result++;
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
int main() {
|
|
initialise_primes(2'000'000);
|
|
|
|
std::cout << "The first 100 Goldbach numbers:" << std::endl;
|
|
for ( int32_t n = 2; n < 102; ++n ) {
|
|
std::cout << std::setw(3) << goldbach_function(2 * n) << ( n % 10 == 1 ? "\n" : "" );
|
|
}
|
|
|
|
std::cout << "\n" << "The 1,000,000th Goldbach number = " << goldbach_function(1'000'000) << std::endl;
|
|
}
|