TopCoder SRM524 Div1 Easy 250 MagicDiamonds

概要

$ n $ を素数でない正整数の和として表したい. 必要な数の個数の最小値を答えよ.

制約

$ 1 \le n \le 10^{12} $.

解法

$ n $ が素数でないなら $ 1 $. 素数なら, $ n - 1 $ と $ 1 $ で分けたくなる.

$ n $ と $ n - 1 $ が両方素数である, $ 3 $ がコーナーケース.

ソースコード

1
2
3
4
5
6
7
8
9
// 245.71 pts

long long MagicDiamonds::minimalTransfer( long long n ){
    if(!isPrime(n)) return 1;
    if(n == 3) return 3;
    return 2;
}

// vim:set foldmethod=marker commentstring=//%s: