直接搜尋因式分解

直接搜尋因式分解是最簡單（也最簡單粗暴）的素因數分解演算法。它透過系統地執行試除法來搜尋一個數的因數，通常使用遞增的數字序列。通常排除小素數的倍數以減少試除數的數量，但有時直接包含它們比排除它們所需的時間更快。直接搜尋因式分解非常低效，只能用於相當小的數字。

當對數字 使用此方法時，只需測試直到 的因數（其中 是向下取整函式）。這是正確的，因為如果所有小於此值的整數都已嘗試過，那麼

(1)

換句話說，所有可能的因數都已經測試過它們的餘因子。同樣成立的是，當 的最小素因數 大於 時，其餘因子 （使得 ）必須是素數。為了證明這一點，假設最小的 大於 。如果 ，那麼 和 可以假設的最小值是 。但是這樣

(2)

這不可能成立。因此， 必須是素數，所以

(3)