A. Bachgold Problem

Codeforces

IDCF749A

Time1000ms

Memory256MB

Difficulty—

greedyimplementationmathnumber theory

English · Original

Chinese · Translation

Formal · Original

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. Recall that integer _k_ is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and _k_. ## Input The only line of the input contains a single integer _n_ (2 ≤ _n_ ≤ 100 000). ## Output The first line of the output contains a single integer _k_ — maximum possible number of primes in representation. The 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. [samples]

Bachgold 问题非常容易表述。给定一个正整数 $n$，将其表示为 *尽可能多* 的素数之和。可以证明，对于任意大于 $1$ 的整数，这样的表示都存在。回忆一下，整数 $k$ 被称为 #cf_span(class=[tex-font-style-underline], body=[prime])，如果它大于 $1$ 且恰好有两个正整数因数 —— $1$ 和 $k$。输入的唯一一行包含一个整数 $n$ ($2 ≤ n ≤ 100 000$)。输出的第一行包含一个整数 $k$ —— 表示中素数的最大可能个数。第二行应包含 $k$ 个素数，它们的和等于 $n$。你可以按任意顺序输出它们。如果有多个最优解，输出任意一个即可。 ## Input 输入的唯一一行包含一个整数 $n$ ($2 ≤ n ≤ 100 000$)。 ## Output 输出的第一行包含一个整数 $k$ —— 表示中素数的最大可能个数。第二行应包含 $k$ 个素数，它们的和等于 $n$。你可以按任意顺序输出它们。如果有多个最优解，输出任意一个即可。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the input integer, with $ 2 \leq n \leq 100{,}000 $. Let $ \mathbb{P} $ denote the set of prime numbers. **Constraints** $ n \geq 2 $ **Objective** Find the maximum integer $ k \in \mathbb{Z}^+ $ and a multiset $ \{p_1, p_2, \dots, p_k\} \subseteq \mathbb{P} $ such that: $$ \sum_{i=1}^{k} p_i = n $$ and $ k $ is maximized.

Samples

Input #1

Output #1

2
2 3

Input #2

Output #2

3
2 2 2

API Response (JSON)

{
  "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 in...",
      "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输入的唯一一行包含一...",
      "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** ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments