UVA – 543 – Goldbach’s Conjecture

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

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

		int i = 0, n = -1;
		while ((n = in.nextInt()) != 0) {
			for (i = 1; i <= primes[0]; i++) {
				if (primes[i] <= primes[primes[0] - 1] && p[n - primes[i]]) {
					System.out.printf("%d = %d + %d\n", n, primes[i], n
							- primes[i]);
					break;
				}
			}
			if (i == primes[0] + 1)
				System.out.println("Goldbach's conjecture is wrong.");
		}
	}

	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: