math - 如何在 spoj 上解决 ALICESIE。它的答案如何有共同的模式

Question

在 spoj 上的问题ALICESIE中，模式 ie(ans=(n+1)/2) 背后的逻辑是什么。

Algorithm_given:
1.创建一个从 N 到 2 (N, N-1, N-2, ..., 3, 2) 的连续整数列表。所有这些 N-1 号码最初都没有标记。
2. 最初，让 P 等于 N，并且不要标记这个数字。
3. 标记 P 的所有适当因数（即 P 保持未标记）。
4.从 2 到 P – 1 中找到最大的未标记数，现在让 P 等于这个数。
5.如果列表中没有更多未标记的数字，请停止。否则，从第 3 步开始重复。

找出未标记数字的总数。

我知道它的 O(sqrt(n)) 解决方案，但在 O(1) 中可以得到答案，它可以通过查看常见模式 ie(N+1)/2 来找到，
但如何证明它数学

链接：ALICESIE

标签： mathnumber-theory