Goldbachova domněnka

O(n log log n)

Goldbachova domněnka (1742, dosud nedokázaná) tvrdí, že každé sudé celé číslo větší než 2 je součtem dvou prvočísel. Tento vizualizér bere největší sudé číslo ≤ n a prochází prvočísla p od 2 nahoru, testuje, zda n−p je také prvočíslo. První taková dvojice je Goldbachův rozklad a je zvýrazněna zeleně; všechna prvočísla vyzkoušená a odmítnutá jsou hnědá. Domněnka byla počítačově ověřena až do 4×10¹⁸. Pokud je n liché, použije se n−1.

Čísla
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Prosej všechna prvočísla do n Eratosthenovým sítem
  2. Procházej prvočísla p od 2 nahoru, testuj zda n−p je také prvočíslo
  3. Zvýrazni první platný pár (p, n−p) zeleně
  4. Výpis p + q = n

Pseudokód

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