P5535 【XR-3】小道消息

先介绍伯特兰·切比雪夫定理：伯特兰—切比雪夫定理说明：若整数n＞3，则至少存在一个质数p，符合n＜p＜2n − 2。另一个稍弱说法是：对于所有大于1的整数n，至少存在一个质数p，符合n＜p＜2n。

知道这个之后这道题就很简单了，我们先简单想想一个质数在一天可以通知除去它的倍数的所有数。
那我们来分讨一下：

1.如果k+1为质数，且 $ \frac{n}{2} \leq k+1 \leq n $,那它通知所有人只需要一天。

2.如果k+1为质数， 且$ 3 \leq k+1 \leq \frac {n}{2}$ , 它必然无法在一天里通知它位于$ \frac {n}{2} - n$里的倍数，于是它需要两天才能通知完所有人。

3.如果一个数是合数，它第一天一定无法通知所有人，根据伯特兰·切比雪夫定理它一定会通知一个位于 $ \frac{n}{2} \leq k+1 \leq n $ 质数，那它在第二天也一定能通知完所有人。

这道题到这就结束了，题目比较简单，主要是了解一下伯特兰·切比雪夫定理 , 对证明感兴趣的可以到百度看看。