They just look for counterexamples. Say, for Goldbach: is_prime(n) { for (i = 2; i < n; i++) if (n % i == 0) return false; // sorry, this

They just look for counterexamples. Say, for Goldbach: is_prime(n) { for (i = 2; i < n; i++) if (n % i == 0) return false; // sorry, this isn't prime return true; // no divisors found, prime } main() { for (i = 4; ;i += 2) { // consider all even numbers i > 2 for (j = 2; j <= i-2; j++) { // consider i as the sum j + (i-j) if (is_prime(j) && is_prime(i-j)) break; // both are prime, so i is a sum of two primes } if (j > i-2) // oops, we checked all js and nothing was found return i; // i is an even number but not a sum of two primes } } You can compile such program yourself and run it to see if it stops ;) Just remember to use some bignum library instead of plain ints.