AOJ0056 Goldbach's Conjecture

AOJ Volume0

問題リンク Goldbach's Conjecture

  • 解法

素数見てからエラトステネス余裕でした。
組み合わせ数を答えるので(a,b)と(b,a)は区別されません。
ここは、a<=n/2までループを回し、aとn-aが共に素数であるかを調べて解きました。

  • ソース
import java.util.Arrays;
import java.util.Scanner;

//Goldbach's Conjecture
public class AOJ0056 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		boolean[] p = new boolean[50001];
		Arrays.fill(p, true);
		p[0] = p[1] = false;
		for(int i=2;i<50001;i++)if(p[i])for(int j=i*2;j<50001;j+=i)p[j]=false;
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			int c = 0;
			for(int i=2;i<=n/2;i++)if(p[i]&&p[n-i])c++;
			System.out.println(c);
		}
	}
}