You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1.3 KiB
1.3 KiB
一、如何判断一个数字开方后的范围
办法：确定上下完全平方数
例1：
\LARGE 9 < 15 < 16 \\
\Rightarrow \\
\sqrt{9} < \sqrt{15} < \sqrt{16} \\
\Rightarrow \\
3 < \sqrt{15} < 4
例2：
\LARGE 25 < 27 < 36 \\
\Rightarrow \\
\sqrt{25} < \sqrt{27} < \sqrt{36} \\
\Rightarrow \\
5 < \sqrt{27} < 6
二、枚举小质数因子的范围
办法：2\sim \sqrt{n}
以15为例：\large \displaystyle 2 \sim \sqrt{15}
因为:\large 3 < \sqrt{15} < 4
也就说，枚举不到4,最多到3。也就是枚举了两个质数2,3,结果发现，只有3有资格成为15的因子。
但问题是15明显还有一个大因子5啊！
是的，当发现15\%3=0时，会把15/3,也就是把3这个因子干掉。
如果枚举到开平方后，发现还不是数字1,就表示还存在一个大的质数因子，直接加进去就行了。
三、为什么如果有大的质数因子，就只能有一个，不能有两个呢？
比如我们对于数字a,假设它存在两个大的质数因子，分别是b,c,则有：\LARGE b>\sqrt{a},c>\sqrt{a}
那么\LARGE b*c>\sqrt{a} * \sqrt{a} =a$$
也就是