Trial division is the most laborious but easiest to understand of the integer factorization algorithms.
Clearly, it is only worthwhile to test candidate factors less than n, and in order from two upwards because an arbitrary n is more likely to be divisible by two than by three, and so on.
Therefore, the effort can be reduced by selecting only prime numbers as candidate factors.
A more complicated implementation only testing primes would be significantly faster in the worst case.
For a base-2 n digit number a, if it starts from two and works up only to the square root of a, the algorithm requires trial divisions, where
This does not take into account the overhead of primality testing to obtain the prime numbers as candidate factors.
Preparing such a table (usually via the Sieve of Eratosthenes) would only be worthwhile if many numbers were to be tested.
Thus, when confronted by an arbitrary large a, it is worthwhile to check for divisibility by the small primes, since for
Because these methods also have superpolynomial time growth a practical limit of n digits is reached very quickly.