TopCoder SRM 524(11/18 01:00~03:00)

MagicDiamonds

非負整数nを非素数の和で表した時，項の数の最小値はいくつか．

nが非素数の場合

1を返す．

nが素数の場合

2ならば，1+1となるので，2を返せば良い．
その他の場合は奇素数なので，n=1+2mと表せるが，
m=1（即ちn=3）の時は，2mが素数なので，3=1+1+1と表わす他ない．
m>1ならば，2mが非素数であるため，2を返せば良い．

よりシンプルに書くと以下のようになる．

public long minimalTransfer(long n){
	return isPrime(n)?1+minimalTransfer(n-1):1;
}

boolean isPrime(long n){
	for(long i=2; i*i<=n; i++){
		if(n%i==0){
			return false;
		}
	}
	return n>1;
}

Challenge Phase

自分も騙されたn=3のケースで1人撃墜．

Result

o-- +1/-0 125.18pts. 491th
1782 -> 1704