4.2 Trial division

If N = a ^. b is a factoring of a number N, then at least one of the numbers a, b is such that its square is not more than N. Thus to check, whether N is a prime, it is enough to test whether it is a multiple of prime number p so that p² is not more than N. This leads to the first test that does not require a list of all primes less than N. Given the increasing sequence l of all primes less than some number x so that x² > N, we check for the primality of N as follows. We run through the sequence l, dividing N by the primes l_i to obtain N = q_il_i + r_i. If r_i is zero then N is not a prime and we stop. If q_i < l_i, then l_i² > N so have checked enough prime factors to show that N is a prime and we stop.