読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #270, A : Design Tutorial: Learn from Math

問題概要

 整数 n ( 12 \leq n \leq 10^6 ) が与えられる。n を 2 つの合成数の和で表わせ。

解法

 4 以上の偶数が全て合成数であることを利用して解きます。n の奇偶によって、

  • n が偶数のとき、n - 6 は合成数(偶数である合成数ならなんでもよい)
  • n が奇数のとき、n - 9 は合成数(奇数である合成数ならよいが、これは 9 のみ)

です。従って、6 または 9 との和に分解すれば、どちらも合成数になります。

コード

readInt = ( readLn :: IO Int )
which a b f = if f then a else b

main = do
	n <- readInt

	let
		m = which 6 9 $ even n 
	
	printf "%d %d\n" m ( n - m )