UVA – 686 – Goldbach’s Conjecture (II)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		boolean[] p = sieve((1 << 15) + 5);
		int[] primes = primes(p);
		Scanner in = new Scanner(System.in);

		int i = 0, n = -1, count;

		while ((n = in.nextInt()) != 0) {

			for (i = 1, count = 0; primes[i] <= (n + 1) / 2; i++)
					if (p[n - primes[i]])
						count++;

			System.out.println(count);
		}
	}

	public static boolean[] sieve(int n) {
		boolean[] p = new boolean[n];

		Arrays.fill(p, true);
		for (int i = 2; i < n; i = (i == 2) ? 3 : i + 2) {
			for (int j = i * 2; p[i] && j < n; j += i) {
				p[j] = false;
			}
		}

		return p;
	}

	public static int[] primes(boolean[] p) {
		int[] ps = new int[p.length];
		for (int i = 2; i < p.length; i++) {
			if (p[i])
				ps[++ps[0]] = i;
		}

		return ps;
	}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: