Prime Coins

最初に動的計画法が思いつくと思われますが、$N\le 10^{18}$ から現実的ではありません。さらに素数判定も行うことができません。ミラーラビン素数判定法を用いたとしても、該当する素数を調べるために $1$ から $N$ 以下の正整数を調べないといけなくなります。

どの方法でも解く術はありません。唯一あるとしたら、$O(1)$ で解くことなど定数時間で解くことがカギです。

問題から「相異なる複数の素数の和が $N$ にすることができるか？」という問題にできるので、この問題文から $O(1)$ で解く必要があります。
$N\le 10^{18}$ であり、$p_n\ge 10^{18}$ であることから、これはRichertの定理を適用することができます。

この定理によると、「$6$ より大きい整数は相異なる複数の素数の和で表すことができる」ことが証明されています。したがって $N\gt 6$ のすべての場合について答えは Yes です。また $N\le 6$ を考えると、素数の和で表せない整数は $N=1,4,6$ のみです( $N=4$ では $p_1=2$ 円硬貨を $2$ 枚使えばいいが、$1$ 枚しかないので払うことができない。それか $1,3$ 円硬貨を使えばよいが、$1$ は素数ではないのでその硬貨は存在しない )。

以上から $N=1,4,6$ に限り素数の和で表せず、それ以外の場合では必ず表すことができます。よってこの問題を $O(1)$ で解くことができました。