Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Goldbach's Conjecture (II)

686.c

/* Goldbach's Conjecture */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int num_primes=0;
int * list_primes=NULL;

int primes_to_n(int n)
{
	int *t, i,j,k;

	if (n<2) {
		return 0;
	}
	if (num_primes) if (n<=list_primes[num_primes-1]) {
		for(i=0; i<num_primes; i++) {
			if (list_primes[i]>n) {
				return i;
			}
		}
		return i;
	}
	t = list_primes = realloc(list_primes, n*sizeof(int));
	if (num_primes==0) {
		t[0]=2;
		num_primes=1;
	}

	i = num_primes-1;
	k = (t[i]+1) | 1;
	while(k<=n) {
		for(j=1; j<i; j++) {
			div_t d = div(k,t[j]);
			if (d.rem==0) {
				break;
			} else if (d.quot < t[j]) {
				j=i;
				break;
			}
		}
		if (j>=i) {
			t[++i] = k;
		}
		k += 2;
	}
	return (num_primes = i+1);
}

int trial_division(int n, int B)
{
	int i,k = primes_to_n(B);

	for(i=0; i<k; i++) {
		if (n%list_primes[i] == 0) {
			return 0;
		}
	}
	return 1;
}

int is_prime(int n)
{
	return trial_division(n, sqrt(n));
}

int main(void)
{
	int i,num;
	int N;

	while(1) {
		scanf("%d", &num);
		if (num==0) {
			exit(0);
		}
		if (num==4) {
			printf("1\n");
			continue;
		}
		N=0;
		for(i=3; i<=num/2; i++) {
			if (is_prime(i) && is_prime(num-i)) {
				N++;
			}
		}
		printf("%d\n", N);
	}
	exit(0);
}