Goldbach's conjecture

O(n log log n)

Goldbach's conjecture (1742, still unproven) asserts that every even integer greater than 2 is the sum of two primes. Given n, this visualiser takes the largest even number ≤ n and scans upward through primes p, testing whether n−p is also prime. The first such pair is the Goldbach partition and is highlighted green; all primes tried and rejected are coloured tan. The conjecture has been verified computationally up to 4×10¹⁸. If n is odd, n−1 is used and noted in the done event.

Numbers
Edit the input and press Play

How it works

  1. Sieve all primes up to n with Eratosthenes
  2. Scan primes p from 2 upward, testing if n−p is also prime
  3. Highlight the first valid pair (p, n−p) green
  4. Report p + q = n

Pseudocode

1goldbach(n):                        # O(n log log n) sieve + O(n) scan2  target = n if even else n - 13  isPrime = eratosthenes(target)4  for p = 2 to target/2:5    if isPrime[p] and isPrime[target - p]:6      return p, target - p         # first Goldbach partition