题目描述

小红拿到一个整数$x$，并希望通过如下两个操作将$x$变为完全平方数。

1. 如$x$是素数，则将其减1

模拟+素数筛

由于$x$不超过$10^9$，所以，如果其为一个完全平方数，则$\sqrt{x}\le\sqrt{10^9}$。同样的，当$x$不是素数时，其最小因子也不会超过$\sqrt{10^9}$。

反证：假设其最小因子$p\gt \sqrt{10^9}$，则有$p'=x/p\lt\sqrt{10^9}$。矛盾。

所以我们需要筛出$\sqrt{10^9}$以内的素数，如果$x$是合数，则在筛出的素数中找最小素因子。如果$x$是素数，那么其要么就在筛出的素数里面，要么就是可以通过$\sqrt{N}$的计算来判断其是否是素数。

假设一个数所有因子均为2，有$2^{30}\gt10^9$，操作一的次数和操作二的次数最多一样，而操作二不会超过30次，所以不会超时。