檢查除數直到max {2≤i≤n}（min（i，n/i））？

Question

我的教授給了另一種解釋爲通過回覆此檢查，直到開方（N）：

「我們需要檢查除數只能做到最大 _{2≤我＆le; N}（分（I，N/I）） 當i = n/i時，達到最大值，即i = sqrt n。「

他甚至指的是什麼？有人可以用英文嗎？

Answer 1

爲您格式化TeX，即「最大 = i < = n（min（i，n/i））」。在英語中，i和n/i中的較小值的最大值在i的所有值從2直到n。

例如，如果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的值，直到最大值 - 這是您的老師給您的表達的值。