直接搜索因式分解

直接搜索因式分解是最简单（也最简单粗暴）的素因数分解算法。它通过系统地执行试除法来搜索一个数的因数，通常使用递增的数字序列。通常排除小素数的倍数以减少试除数的数量，但有时直接包含它们比排除它们所需的时间更快。直接搜索因式分解非常低效，只能用于相当小的数字。

当对数字 使用此方法时，只需测试直到 的因数（其中 是向下取整函数）。这是正确的，因为如果所有小于此值的整数都已尝试过，那么

(1)

换句话说，所有可能的因数都已经测试过它们的余因子。同样成立的是，当 的最小素因数 大于 时，其余因子 （使得 ）必须是素数。为了证明这一点，假设最小的 大于 。如果 ，那么 和 可以假设的最小值是 。但是这样

(2)

这不可能成立。因此， 必须是素数，所以

(3)