A high-performance C++ implementation for verifying Goldbach's conjecture - the famous unsolved mathematical problem stating that every even integer greater than 2 can be expressed as the sum of two prime numbers.

This program efficiently tests Goldbach's conjecture for given even numbers using the Sieve of Eratosthenes algorithm for prime number generation. It provides both fast single-pair discovery and comprehensive enumeration of all valid prime pairs.

• Efficient Prime Generation: Uses Sieve of Eratosthenes for O(n log log n) prime generation
• Flexible Operation: Find first prime pair or enumerate all possible pairs
• Performance Timing: Built-in benchmarking to measure processing time
• Command-Line Interface: Support for both interactive and batch processing
• Comprehensive Error Handling: Robust input validation and error reporting
• 64-bit Integer Support: Handles large numbers up to the limits of int64_t
• Modular Design: Clean separation of concerns with dedicated classes

• C++17 compatible compiler (GCC, Clang, or MSVC)
• Make (optional, for using Makefile)

make

# Compile main program
g++ -std=c++17 -o goldbach main.cpp goldbach.cpp

# Compile test suite
g++ -std=c++17 -o test_goldbach test_goldbach.cpp goldbach.cpp

# Compile with optimizations
g++ -std=c++17 -O3 -DNDEBUG -o goldbach main.cpp goldbach.cpp

# Interactive mode (prompts for input)
./goldbach

# Direct number input
./goldbach 28

# Find all prime pairs
./goldbach -a 28

# Show help
./goldbach --help

• -a, --all: Find all prime pairs (default: find first only)
• -h, --help: Display usage information

$ ./goldbach 28
Goldbach's conjecture verified for 28:
  5 + 23 = 28
Found 1 prime pair
Processing time: 0.002786 ms

$ ./goldbach -a 28
Goldbach's conjecture verified for 28:
  5 + 23 = 28
  11 + 17 = 28
Found 2 prime pairs
Processing time: 0.005515 ms

$ ./goldbach
Enter an even number (>= 4): 100
Goldbach's conjecture verified for 100:
  3 + 97 = 100
Found 1 prime pair
Processing time: 0.003214 ms

$ ./goldbach -a 1000000
Goldbach's conjecture verified for 1000000:
  17 + 999983 = 1000000
  41 + 999959 = 1000000
  ... (many more pairs)
Found 5402 prime pairs
Processing time: 23.456 ms

Run the comprehensive test suite to verify functionality:

./test_goldbach

The test suite includes:

• Prime number validation
• Goldbach conjecture verification
• Error handling tests
• Performance benchmarks
• Known value verification

• Purpose: Efficient prime number generation and testing
• Algorithm: Sieve of Eratosthenes with fallback brute-force
• Methods:
  • isPrime(int num): Test if a number is prime
  • getPrimesUpTo(int n): Get all primes up to n
  • generateSieve(int n): Generate prime sieve up to n

• Purpose: Verify Goldbach's conjecture for given numbers
• Methods:
  • verifyConjecture(int number, bool findAllPairs): Main verification method
  • printResult(const GoldbachResult& result, int number): Display results

• Purpose: Store verification results with performance metrics
• Fields:
  • found: Whether prime pairs were found
  • primePairs: Vector of valid prime pairs
  • processingTimeMs: Processing time in milliseconds

• Prime Generation: O(n log log n) using Sieve of Eratosthenes
• Goldbach Verification: O(n) for finding all pairs, O(k) for first pair where k < n/2
• Space Complexity: O(n) for prime sieve storage

The program demonstrates excellent performance characteristics:

Formulated by Christian Goldbach in 1742, the conjecture states:

"Every even integer greater than 2 can be expressed as the sum of two primes."

• Verified computationally for all even numbers up to 4×10^18
• No counterexamples found
• Remains one of mathematics' oldest unsolved problems

1. Generate all primes up to the target number using Sieve of Eratosthenes
2. Iterate from 2 to n/2, checking if both i and n-i are prime
3. Collect valid pairs and return results with performance metrics

• Follow C++17 standards
• Use meaningful variable names
• Include comprehensive error handling
• Add unit tests for new functionality

• Add test cases for edge conditions
• Verify performance with large inputs
• Test error handling scenarios

This project is licensed under the MIT License - see the LICENSE file for details.

Sahil-Muhammed (c) 2025

• Complete rewrite with modular architecture
• Sieve of Eratosthenes implementation
• Command-line interface with argument parsing
• Comprehensive test suite
• Performance benchmarking
• 64-bit integer support

• Basic implementation with brute-force prime checking
• Single pair discovery only
• Interactive input only
• No error handling or testing