# [Community Puzzle] Number derivation

https://www.codingame.com/training/easy/number-derivation

Created by @nicola,validated by @ViktorCs,@Scarlatine and @Vestiaz.
If you have any issues, feel free to ping them.

I donâ€™t understand, what exactly I should do. Even by looking at the test cases, I still have no clue. Is every integer n either a prime or a product of primes?

Yes, every positive integer is a product of primes: https://en.wikipedia.org/wiki/Integer_factorization

An example of how you can solve Testcase 4:
n = 42
42 = 2 * 21
42â€™ = (2 * 21)â€™ = 2â€™ * 21 + 2 * 21â€™ = 21 + 2 * 21â€™
21â€™ = (7*3)â€™ = 7â€™ * 3 + 3â€™ * 7 = 1 * 3 + 1 * 7 = 10
=> 42â€™ = 21 + 2 * 10 = 41

1 Like

Yes, except 1 and 0.
Itâ€™s the fundamental theorem of arithmetic.

I changed â€śgiven numberâ€ť for â€śgiven positive integerâ€ť to make it clearer - though you can guess it easily from the â€śarithmeticsâ€ť tag and itâ€™s stated later than the number is >1.

Does this work for numbers with four prime numbers as for eg:210 goes on

Of course.

Great puzzle. Code implementation turned out to be quite short, but this shook some rust off my math knowledge.

1 Like