factorization - 如何获得范围内数字的因子数？

Question

通常我会进行素数分解并获得所有素数，然后我会进行排列和组合以找到所有因数。

例如：1824 是我要考虑的数字。现在我需要 300 中的 1824 的无因数。

有什么诀窍吗？？

Answer 1

一个技巧是不要搜索超过您正在搜索因子的数字的平方根的数字。例如，要从 2-300 中查找因子，您只需要从 2-ceil(sqrt(1824)) 中搜索，即 2-43。找到 2-43 范围内的数字后，将其分成 1824 以检查可能高于 43 的其他因素。

Answer 2

作为蛮力解决方案，您不需要为此对数字进行素数分解。您可以简单地检查范围内的所有数字。

让您希望找到因子的数字范围为 [range_start, range_end]。只需在循环中遍历这些数字，并为每个数字（比如 x）检查 if ( number % x == 0)，如果是，则 x 是数字的一个因子。