math - 检查除数直到 max{2 ≤ i ≤ n} (min (i,n/i))？

Question

我的教授通过回复以下内容给出了检查直到 sqrt(n) 的另一种解释：

“我们只需要检查除数直到最大值_{2 ≤ i ≤ n} (min(i, n/i))。当 i = n/i 时达到最大值，即 i = sqrt n。”

他到底是什么意思？有人能用英文写吗？

Answer 1

为您格式化 TeX，即“max _{2 <= i <= n} (min(i, n/i))”。在英语中，从 2 到的所有值中的较小i者的最大值。n/iin

例如，如果n是 12：

i    n/i    min(i,n/i)
2    6      2
3    4      3    <--- Largest value is 3: sqrt(12) rounded down
4    3      3
5    2      2
6    2      2
7    1      1
8    1      1
9    1      1
10   1      1
11   1      1 
12   1      1

很容易看出i < n/i当且仅当i < sqrt(n)，并且从中我们可以看到该表达式的最大值将是sqrt(n)。

据推测，这是为了找到 的因数n。如果i是一个因子，那么n/i也是，因为n/i * i = n，所以没有必要同时测试i和n/i。因此，我们可以选择只检查两者中较小的一个，min(i, n/i)，并且只需要考虑i到最大的值——这是你的老师给你的表达式的值。