TopCoder, SRM 617, Division 2, Level 1 : SilverbachConjecture

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13139&rd=15850

問題概要

　正整数 n が与えられる。合成数である x, y の組であって、x + y = n を満たすものを一つ求めよ。

解法

　まず、x を決めると条件を満たす y は n - x と定まるので、n の分割は 個です。この程度ならば、一つの組に対する処理がよほど重くない限りは Time Limit に間に合います。あとは、x, y を仮定したとき、それが合成数に関する条件を満たすかどうかを求められれば問題を解くことができます。
　さて、「合成数である」とは「素数ではない」と同値なので、正整数に対する素数判定をできればよいということになります。試し割りによる の方法で十分間に合うと思います。わたしは Eratosthenes の篩をライブラリ化していて、ある数が素数か否かの表を簡単に作れたのでそれで解きました。

コード

using VI = vector<int>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

// 素数かどうかの表を計算
// Eratosthenes の篩 : O( N log log N )
vector<bool> eratosthenes( const int N );

class SilverbachConjecture
{
public:
	vector <int> solve( int n )
	{
		auto isPrime = eratosthenes( 2000 );

		REP( i, 2, n - 1 )
		{
			if ( !isPrime[i] && !isPrime[ n - i ] )
			{
				return VI{ i, n - i };
			}
		}
		return VI();		
	}
};