La Conjetura de Goldbach

La conjetura de Goldbach se divide en dos variantes: la conjetura doble y la conjetura triple. La conjetura doble establece que todo número par mayor o igual a 6 puede expresarse como la suma de dos números primos impares. La conjetura triple afirma que todo número impar mayor o igual a 9 puede representarse como la suma de tres números primos impares. Nota: el número 1 no se considera primo.

En un desafío de programación típico, se solicita generar los números pares entre 6 y 100,000 que puedan descomponerse como la suma de dos números primos impares, es decir, a = b + c. El programa debe imprimir b y c; si existen múltiples combinaciones, basta con mostrar una. Se debe priorizar la eficiencia temporal.

Para resolver esto, primero se necesitan calcular números primos. Una técnica es usar espacio para ganar tiempo: precomputar todos los primos menores que 100,000 y almacenarlos en un arreglo. Luego, emplear dos punteros, uno al inicio y otro al final del arreglo, para buscar combinaciones. Sin embargo, el desafío principal radica en calcular los primos de manera eficiente.

Métodos para Calcular Números Primos

Método 1: Verificación por División Directa

Según la definición, un número primo solo tiene dos divisores: 1 y él mismo. La forma más simple es verificar si un número n es divisible por algún entero entre 2 y n-1.

bool esPrimo(int n) { for (int divisor = 2; divisor < n; divisor++) { if (n % divisor == 0) { return false; } } return true; }

</div>### Método 2: Optimización con Raíz Cuadrada

Si n es divisible por un número x, entonces también es divisible por n/x. Por lo tanto, solo es necesario verificar divisores hasta la raíz cuadrada de n.

<div>```

bool esPrimo(int n) {
    for (int divisor = 2; divisor * divisor <= n; divisor++) {
        if (n % divisor == 0) {
            return false;
        }
    }
    return true;
}

Método 3: Criba de Eratóstenes

La idea es eliminar los múltiplos de los números primos conocidos. Se comienza con una lista de números y se marcan los múltiplos de cada primo encontrado.

#define LIMITE 1000 bool esPrimo[LIMITE]; void inicializarPrimos() { for (int num = 2; num < LIMITE; num++) { esPrimo[num] = true; } for (int base = 2; base < LIMITE; base++) { if (esPrimo[base]) { for (int multiplo = base * 2; multiplo < LIMITE; multiplo += base) { esPrimo[multiplo] = false; } } } }

</div>Después de ejecutar, esPrimo\[i\] será verdadero si i es primo. La complejidad temporal es O(n log log n).

### Método 4: Criba Mejorada

Se puede usar un arreglo adicoinal para almacenar los primos encontrados y usarlos para filtrar más números, aprovechando que todo número compuesto tiene un factor primo.

<div>```

#define LIMITE 1000
bool esPrimo[LIMITE];
int primosEncontrados[LIMITE];
void calcularPrimos(int max) {
    memset(esPrimo, 0, sizeof(esPrimo));
    memset(primosEncontrados, 0, sizeof(primosEncontrados));
    int contador = 0;
    for (int i = 2; i <= max; i++) {
        if (!esPrimo[i]) {
            primosEncontrados[contador++] = i;
        }
        for (int j = 0; j < contador && primosEncontrados[j] * i <= max; j++) {
            esPrimo[primosEncontrados[j] * i] = true;
            if (i % primosEncontrados[j] == 0) break;
        }
    }
}

Para números grandes como 100,000, en lugar de precomputar todos los primos, se puede buscar primos alrededor de la mitad del número. Por ejemplo, para un número par a, buscar primos b y c tales que b + c = a, con b y c cercanos a a/2. Se puede iterar desde 1 hasta a/2, verificando si a/2 - i y a/2 + i son primos.