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.
|
|
|
|
|
### 一、如何判断一个数字开方后的范围
|
|
|
|
|
|
<font color='red' size=5><b>办法：确定上下完全平方数</b></font>
|
|
|
|
|
|
|
|
|
|
|
|
**例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$$
|
|
|
|
|
|
|
|
|
|
|
|
也就是$$$$
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
