オリジナル問題 加藤のお買い物

オリジナル問題です.

問題

加藤さんは10^{100}以下の素数の硬貨2円,3円,5円,7円,...をそれぞれ10^{100}枚持って買い物にきました.
加藤さんがN円の商品をお釣りがないように手持ちで支払うとき, 用いる硬貨の枚数の最小値はいくつでしょうか？

制約

2 \leq N \leq 10^7

解法

前回の三角数の問題に触発されて, この問題を思いつきました.
DPやらなんやらをやるとTLEすると思います.
こんな未解決問題があります.
ゴールドバッハの予想 - Wikipedia
4以上の偶数は2つの奇素数の和で表すことができる, という予想です. しかも未解決問題で, ミレミアム懸賞金もかかっていますが, 4 \times 10^{18}までの偶数においてこの性質が成り立つことは証明されています(http://sweet.ua.pt/tos/goldbach.html). よってその範囲内でこれを用いることができます.
問題に戻ります.
与えられたNについて場合分けします.

①Nが素数であったとき

硬貨は１つのみで済むので1を出力します.

②Nが偶数であったとき

上の予想より2つの素数の和でNを表すことができるため, 2を出力します.

③Nが素数でない奇数であったとき

この場合が少しややこしいです. まず, 2,3,4,5,6,7,8までは①,②で尽くされているため, N \geq 9で考えます. また, Nが素数である場合も①で尽くされているとします.
このとき, 例えば3を支払うと決め打ちすると. N-3は必ず偶数になり, このとき上の予想が成り立つので支払う硬貨の枚数の上界は3であることがわかります.
硬貨2枚で払うときを考えます. 素数でない奇数を2数の和で表すためには, N = (奇数) + (偶数) の組み合わせとなることが必要です. 唯一持っている偶数は2のみであり, このときにN-2が素数であれば, 硬貨2枚で支払いが行えます. この条件を満たさないときは3枚の硬貨が必要となります.
以上で尽くされました.

その他

制約が2 \leq N \leq 10^7となっていますが, 計算量を見積もるとO(\sqrt{N})であるため, 2 \leq N \leq 10^{14}かもうちょい高くても大丈夫そうです. そのときは制約から解法が透けそうですが...

ソースコード

#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
bool isPrime(ll num){
  ll j = (ll)(sqrt(num))+1;
  if(num == 2)
    return true;
  if((num % 2) == 0)
    return false;
  for(int i=3;i<=j;i+=2){
    if(!(num%i)){
      return false;
      
    }
  }
  return true;
}

int main()
{
  ll N;
  cin >> N;
  if(isPrime(N))
    cout << 1 << endl;
  else if(N % 2 == 0)
    cout << 2 << endl;
  else{
    if(isPrime(N-2))
      cout << 2 << endl;
    else
      cout << 3 << endl;
  }
  return 0;
}