{"problem":{"name":"A. Bachgold Problem","description":{"content":"Bachgold problem is very easy to formulate. Given a positive integer _n_ represent it as a sum of **maximum possible** number of prime numbers. One can prove that such representation exists for any in","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF749A"},"statements":[{"statement_type":"Markdown","content":"Bachgold problem is very easy to formulate. Given a positive integer _n_ represent it as a sum of **maximum possible** number of prime numbers. One can prove that such representation exists for any integer greater than 1.\n\nRecall that integer _k_ is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and _k_.\n\n## Input\n\nThe only line of the input contains a single integer _n_ (2 ≤ _n_ ≤ 100 000).\n\n## Output\n\nThe first line of the output contains a single integer _k_ — maximum possible number of primes in representation.\n\nThe second line should contain _k_ primes with their sum equal to _n_. You can print them in any order. If there are several optimal solution, print any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Bachgold 问题非常容易表述。给定一个正整数 $n$，将其表示为 *尽可能多* 的素数之和。可以证明，对于任意大于 $1$ 的整数，这样的表示都存在。\n\n回忆一下，整数 $k$ 被称为 #cf_span(class=[tex-font-style-underline], body=[prime])，如果它大于 $1$ 且恰好有两个正整数因数 —— $1$ 和 $k$。\n\n输入的唯一一行包含一个整数 $n$ ($2 ≤ n ≤ 100 000$)。\n\n输出的第一行包含一个整数 $k$ —— 表示中素数的最大可能个数。\n\n第二行应包含 $k$ 个素数，它们的和等于 $n$。你可以按任意顺序输出它们。如果有多个最优解，输出任意一个即可。\n\n## Input\n\n输入的唯一一行包含一个整数 $n$ ($2 ≤ n ≤ 100 000$)。\n\n## Output\n\n输出的第一行包含一个整数 $k$ —— 表示中素数的最大可能个数。第二行应包含 $k$ 个素数，它们的和等于 $n$。你可以按任意顺序输出它们。如果有多个最优解，输出任意一个即可。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the input integer, with $ 2 \\leq n \\leq 100{,}000 $.  \nLet $ \\mathbb{P} $ denote the set of prime numbers.\n\n**Constraints**  \n$ n \\geq 2 $\n\n**Objective**  \nFind the maximum integer $ k \\in \\mathbb{Z}^+ $ and a multiset $ \\{p_1, p_2, \\dots, p_k\\} \\subseteq \\mathbb{P} $ such that:  \n$$\n\\sum_{i=1}^{k} p_i = n\n$$  \nand $ k $ is maximized.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF749A","tags":["greedy","implementation","math","number theory"],"sample_group":[["5","2\n2 3"],["6","3\n2 2 2"]],"created_at":"2026-03-03 11:00:39"}}