Trial division

Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than n. For example, for the integer n = 12, the only numbers that divide it are 1,2,3,4,6,12. Selecting only the largest powers of primes in this list gives that 12 = 3 × 4.

Given an integer n (throughout this article, n refers to "the integer to be factored"), trial division consists of systematically testing whether n is divisible by any smaller number. 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. With this ordering, there is no point in testing for divisibility by four if the number has already been determined not divisible by two, and so on for three and any multiple of three, etc. Therefore, effort can be reduced by selecting only prime numbers as candidate factors. Furthermore, the trial factors need go no further than ${\displaystyle \scriptstyle {\sqrt {n}}}$ because, if n is divisible by some number p, then n = p × q and if q were smaller than p, n would have earlier been detected as being divisible by q or a prime factor of q.

A definite bound on the prime factors is possible. Suppose P_i is the i'th prime, so that P₁ = 2, P₂ = 3, P₃ = 5, etc. Then the last prime number worth testing as a possible factor of n is P_i where P²_i + 1 > n; equality here would mean that P_i + 1 is a factor. Thus, testing with 2, 3, and 5 suffices up to n = 48 not just 25 because the square of the next prime is 49, and below n = 25 just 2 and 3 are sufficient. Should the square root of n be integral, then it is a factor and n is a perfect square.

...
Wikipedia