Solución a la Tarea 3: Suma de Primos

Como vamos a necesitar decidir si un número es primo o no en tres lugares distintos de nuestro programa, lo más práctico es escribir una función que efectúe este trabajo. Ya habíamos visto una en clase, la cual es suficiente, pero abajo muestro una forma que es más rápida porque en lugar de revisar todos los números entre 2 y n - 1 como posibles divisores de n, sólo revisa los números entre 2 y la raíz cuadrada de n. ¿Porqué funciona?

int primo(long int n)
{
  long int i;
 
  if (n < 2)
    return 0;
  for (i = 2; i*i <= n; i++)
    if ((n % i) == 0)
      return 0;
  return 1;
}

La función principal resuelve el problema de la forma más natural: Primero verificamos si n es primo. En caso contrario, verificamos si n se puede escribir como suma de dos primos. Observe que para ello sólo verificamos si i y n - i son primos para alguna i que sea menor que o igual a n/2, es decir, no es necesario verificar para todos los valores de i entre 2 y n - 2, y mucho menos para todos los valores de i y j en ese intervalo. ¿Porqué?

int main(void)
{
  long int i, n, n2;
 
  scanf("%ld", &n);
  if (primo(n))
    printf("%ld 0\n", n);
  else {
    n2 = n/2;
    for (i = 2; i <= n2; i++)
      if (primo(i) && primo(n-i)) {
        printf("%ld %ld\n", n-i, i);
        break;
      }
    if (i > n2)
      printf("0 0\n");
  }
  return 0;
}

Decidir si un número (que no es primo) es suma de dos primos se puede hacer más rápido si notamos lo siguiente: Si n = 4 entonces p = 2 y q = 2, si n > 4 es par entonces p y q deben ser primos impares, y si n es impar entonces q = 2 y p = n - 2 debe ser un primo impar. ¿Porqué?

Los valores de entrada y salida (que en este caso no son los únicos posibles) empleados para la evaluación fueron los siguientes:

Entrada      Salida
1            0 0
2            2 0
10           7 3
17           17 0
27           0 0
30           23 7
98           79 19
220          197 23
308          277 31
556          509 47

Para probar su tarea en UNIX, escriban la instrucción gcc sumapNN.c -o sumap para compilar su programa, y la instrucción ./sumap para correrlo. Algunos errores comúnes fueron: (a) Olvidar que 1 es un valor legal de la entrada. (b) Sólo revisar que uno de p y q es primo. (c) Imprimir p y q en desorden. (d) No usar números de tipo long int (aunque no probé con números muy grandes, pues varios programas eran demasiado lentos).