解题思路

把这个过程看成一个“步长不断变化”的约瑟夫环问题。

设报到的素数依次为 $2,3,5,7,11,\dots$ 。

第一次淘汰发生在报到 $2$ 时，因此第一次的淘汰步长是 $2$ 。第二次淘汰发生在报到 $3$ 时，距离上一次只多了 $1$ ，所以第二次步长是 $1$ 。第三次淘汰发生在报到 $5$ 时，距离上一次多了 $2$ ，所以第三次步长是 $2$ 。

题目内容

小红是一个喜欢解决有趣问题的高中生。有一天，他和 $n-1$ 个同学来到学校的操场，他们一起围成了一个圆圈。小红和他的同学们非常兴奋，因为他们要开始一个非常有趣的游戏。

这个游戏的规则非常简单：从1开始报数，每次报数时，如果报到的数字是素数，那么这个人就会被淘汰出游戏。淘汰的人离开圆圈，留下来的人继续报数，直到只有一个人留下来为止。

小红非常聪明，他知道如何用算法来解决这个问题。他开始思考如何计算最后留下来的人的编号，以便告诉他的同学们答案。

现在，小红想请你帮助他计算最后留下来的同学的编号。你需要根据给定的 $n$ ，计算出最后留下来的同学的编号是多少。

素数：只能被 1 和自己整除的数。

一个正整数n。代表学生的人数。

$1≤n≤10^4$

一个正整数，代表最终留下来的学生编号。

输入

输出

输入

输出