Number as sum of prime numbers

[PirateNeko]

I have to make a number as sum of prime numbers with as low as possible terms in C++. I tried making it but the way is too confusing and don`t know where to start.
Eg. 25=1+3+5+7+9
but 25=23+2
The second variant is correct.

[LB]

If you know the maximum input for which you need to do this, you can just store the prime numbers precalculated in an array. In either case, this is just a variant of the classic "Making Change" problem - plenty of information is available online to help you solve this.

[PirateNeko]

The problem is that there isn`t and maximum input. The maximum input is the max of int.

[LB]

In that case, just use memoization and find primes on an as-needed basis.

[Duthomhas]

The 'maximum input' is the number given as input.

Just create a list of primes ≤ input.
Then 'make change'.

[LB]

@Duoas: I was talking about over all possible executions - that is, not actually having any prime finding code and just having a static const array of primes. But yeah, we're saying the same thing in different ways.